Search

Multiple string matching is one of the core techniques of intrusion detection system, where Aho-Corasick al-gorithm is widely used. To solve the problem that huge storage overhead of AC would influence performance deeply, an improved algorithm ——FilterFA, based on specification of character set was proposed. This algorithm compressed large character by the character set mapping function, and constructed a new automata based on the mapped character set,then space complexity decreased to O(|P||Σ′|). Experiments on synthetic datasets and real-world datasets (such as ClamAV) show that the storage overhead of FilterFA is only about 3% of that of AC, while the size of the character set is 8, and the false recognition rate is less than 2%.

Multiple string matching is one of the core techniques of intrusion detection system, where Aho-Corasick al-gorithm is widely used. To solve the problem that huge storage overhead of AC would influence performance deeply, an improved algorithm ——FilterFA, based on specification of character set was proposed. This algorithm compressed large character by the character set mapping function, and constructed a new automata based on the mapped character set,then space complexity decreased to O(|P||Σ′|). Experiments on synthetic datasets and real-world datasets (such as ClamAV) show that the storage overhead of FilterFA is only about 3% of that of AC, while the size of the character set is 8, and the false recognition rate is less than 2%.

The famous multiple string matching algorithm AC consumed huge memory when the string signatures were massive,thus unable to process high speed network traffic efficiently.To solve this problem,a space-efficient multiple string matching algorithm-HashTrie was proposed.This algorithm adopted recursive hash function to store the patterns in bit-vectors in place of the state transition table in order to reduce space consumption.Further more it made use of the rank operation for fast verification.Theoretic analysis shows that the space complexity of HashTrie is O(|P|),which is linear with the size of pattern set |P|and is independent of the alphabetsize σ.The space complexity is superior to the complexity O(|P|σlog|P|)of AC.Experiments on synthetic datasets and real-world datasets(such as Snort,ClamAV and URL)show that HashTrie saves up to 99.6% storage cost compared with AC,and in the meanwhile it runs at a matching speed that is about half of AC.HashTrie is a space-efficient multiple string matching algorithm that is appropriate to search large scale pattern strings with short lengths.

The famous multiple string matching algorithm AC consumed huge memory when the string signatures were massive,thus unable to process high speed network traffic efficiently.To solve this problem,a space-efficient multiple string matching algorithm-HashTrie was proposed.This algorithm adopted recursive hash function to store the patterns in bit-vectors in place of the state transition table in order to reduce space consumption.Further more it made use of the rank operation for fast verification.Theoretic analysis shows that the space complexity of HashTrie is O(|P|),which is linear with the size of pattern set |P|and is independent of the alphabetsize σ.The space complexity is superior to the complexity O(|P|σlog|P|)of AC.Experiments on synthetic datasets and real-world datasets(such as Snort,ClamAV and URL)show that HashTrie saves up to 99.6% storage cost compared with AC,and in the meanwhile it runs at a matching speed that is about half of AC.HashTrie is a space-efficient multiple string matching algorithm that is appropriate to search large scale pattern strings with short lengths.

Despite the fast speed in multiple string matching tasks,the advanced Aho-Corasick(AC) automata wastes storage memory to a great extent.Study indicated that the automata states have specific statistical access characteristics in practice.Accordingly,a series of algorithms based on statistical characteristics for building hybrid finite automata,named HybridFA,are proposed.This work completes partial states of the AC automata according to different features,including access frequency,state hierarchy,and combined characteristics respectively.Experimental results on the real-world datasets like Snort,ClamAV,and URL show that the storage space of HybridAC is reduced to less than 5% of the space cost by the advanced AC automata.Furthermore,HybridFA based on combined characteristics achieves the superior performance on matching speed and robustness comparing to other proposed algorithms.

Despite the fast speed in multiple string matching tasks,the advanced Aho-Corasick(AC) automata wastes storage memory to a great extent.Study indicated that the automata states have specific statistical access characteristics in practice.Accordingly,a series of algorithms based on statistical characteristics for building hybrid finite automata,named HybridFA,are proposed.This work completes partial states of the AC automata according to different features,including access frequency,state hierarchy,and combined characteristics respectively.Experimental results on the real-world datasets like Snort,ClamAV,and URL show that the storage space of HybridAC is reduced to less than 5% of the space cost by the advanced AC automata.Furthermore,HybridFA based on combined characteristics achieves the superior performance on matching speed and robustness comparing to other proposed algorithms.

Establishing a trust system, which considers energy efficiency and a trust metric aware both subjectivity and objectivity in the Internet of Things, is a powerful technique to defend against malicious attacks and improve the per-formance of network. A trust system based on behavior detection was proposed, which takes direct trust, recommended trust as well as history statistical trust into trust evaluation periodically and in communication. Recommended trust and history statistical trust were calculated by evidence combination and Bayes respectively. Simulation results show that nodes occur abnormal behavior could be quickly detected by the proposed trust system and the energy consumption of transmitting recommended trust was saved greatly.

Establishing a trust system, which considers energy efficiency and a trust metric aware both subjectivity and objectivity in the Internet of Things, is a powerful technique to defend against malicious attacks and improve the per-formance of network. A trust system based on behavior detection was proposed, which takes direct trust, recommended trust as well as history statistical trust into trust evaluation periodically and in communication. Recommended trust and history statistical trust were calculated by evidence combination and Bayes respectively. Simulation results show that nodes occur abnormal behavior could be quickly detected by the proposed trust system and the energy consumption of transmitting recommended trust was saved greatly.

Cloud computation provided the capabilities to store and compute infinitely,which can filled the gap of resource constrain.So a cloud-computation based social authentication system for smartphones aimed at the problem that the present authentication methods require a long period of validity of the authentication tokens and make the terminals consume large resources was proposed.The system took three types of social networking features into considered,which were different certification authority between the friends,behavior differences between individual and trust level carried by each interactive event.The results of experiments show that the system can effectively solve the problem that system performance will sharply decline when the expiry date of authentication tokens is short.

Cloud computation provided the capabilities to store and compute infinitely,which can filled the gap of resource constrain.So a cloud-computation based social authentication system for smartphones aimed at the problem that the present authentication methods require a long period of validity of the authentication tokens and make the terminals consume large resources was proposed.The system took three types of social networking features into considered,which were different certification authority between the friends,behavior differences between individual and trust level carried by each interactive event.The results of experiments show that the system can effectively solve the problem that system performance will sharply decline when the expiry date of authentication tokens is short.