vào các phần mềm độc hại. Thay vì cố gắng để pin xuống chính xác những điều khoản này, các đặc điểm chung mỗi loại phần mềm độc hại thường có được liệt kê. Malware có thể được tạm chia thành các loại theo phương pháp của phần mềm độc hại hoạt động. Phần mềm Anti-virus ", | 58 COMPUTER VIRUSES AND MALWARE other other Added hi other other Added hips Added hip other Added hit Figure . Trie building Added chip Figure shows the trie being built incrementally for the running example. The trie s root is the start state of the finite automaton and a self-edge is added to it. A signature is added by starting at the root tracing along existing paths until a necessary edge is absent then adding the remaining edges and states. The end of a path becomes a final state. 2 Label the states in the trie. The trie states are assigned numbers such that states closer to the root have lower numbers. This corresponds to a breadth-first ordering of the states. If the trie states are laid out as in previous figures then numbering is a simple matter of stepping through the columns of states. The breadth-first ordering and labels appear in Figure . 3 Compute the failure function and finish the automaton. The failure function is undefined for the start state but must be computed for all other states. Anti-Virus Techniques 59 other Figure . Trie labeling Any state directly connected to the start state in other words at a depth of 1 in the trie can only resume searching at the start state. For other states the partially-computed failure function is used to trace back through the automaton to find the earliest place the search can resume. Processing states in breadth-first order ensures that needed failure function values are always present. The computation algorithm is below. Notice that it not only fills in the failure function but also updates the finite automaton. The notation r s means an edge from some state r with some label a to state s and state A t is an edge labeled a from state state to some state t. foreach state s where depth s 1 failure s START-STATE foreach state s where depth s 1 in breadth order find the edge r - s state failure r while no edge state t exists state failure state failure s t output s u output t Returning to the .
