Malware Discrimination Based on Reversed Association Task

Regarding the prominent threat of malware and the predicament faced by current identification technology, this paper considers that the primary reason is that the technical features used to identify malware are unstable and user-dependent. Furthermore, an in-depth analysis of those technical features leads us to believe that the root cause lies in the lag of discrimination theory behind practice. Because every piece of software has a specific task or purpose, we propose malware discrimination based on identifying the malicious tasks or purposes. We first present a formal definition of a task and then provide further classifications of malicious tasks. Then, based on decidable theory, we conclude that tasks are decidable, computable and finite, which enables us to prove that they are recursive and determinable. By establishing a map from software to task, we prove that software is many-to-one reducible to corresponding tasks. Thus, we show that software, including malware such as computer viruses, internet worms and Trojan horses, is also recursive and can be determined from the corresponding tasks. Finally, a discrimination process and practical examples are presented to verify our theory. Two key issues are identified for future research on malware discrimination.