# Appilicability of Theoritical Computer Science in Malware research

I would like to know the importance of TCS in Malware research. Due to the large volume of new malware variants received per day (~50,000 samples/day according to McAfee), malware researchers are heavily dependent on dynamic analysis (i.e. running the samples in a sandbox and monitoring their behavior) and moving away from static analysis and Reverse engineering as these approaches are very time consuming and sometimes becomes very challenging due to obfuscation/encryption.

I found a very useful talk (BlackHat 2010) by Greg Hoglund on Malware attribution where the speaker talks about the importance of bringing in the malware authors and their networks into the picture which gives valuable information than just analyzing the binary itself.

I have two questions:

1. If malware researchers move towards analyzing the behavior of malware authors and their network, in the future does TCS has any importance in malware research.
2. As I am not strong in TCS, I would like to know where exactly TCS fits in malware research.

Thank you.

• a lot of malware algorithms are based on databases of hashcodes of "harmful" programs. so hashcode theory is relevant. another area of active research is to create bulletproof "sandboxes"... will cite some refs on this if the question gets upvoted
– vzn
Aug 10, 2012 at 1:41
• Look up semantics based approaches to malware detection for approaches with more theory. Aug 10, 2012 at 6:14
• You might be interested in the question What is the branch of Computer Science that studies how Anti Virus programs work? on CS.SE.
– Juho
Aug 10, 2012 at 8:24
• There's a book called "Malicious Cryptography" with ideas on how TCS can be used in malware. Aug 10, 2012 at 21:13

Fred Cohen is an authority & early researcher on the theory of computer viruses. see that wikipedia page for references. his 1987 paper is given credit as maybe the 1st analogy of the virus checking problem to the halting problem.

the basic idea is to create a program X that calls a virus checking subroutine with a program code as parameter. then, if the subroutine returns "is a virus", exit. if it returns "is not a virus", infect the system. such a program cannot exist by diagonalization/contradiction, passing its own code as the parameter. therefore there is no perfect virus checker.

but it would seem an easy counterargument to this statement could be, program X contains a harmful section of code, and that its irrelevant whether it is called or not-- the program is potentially harmful if it contains any "harmful section of code".

as I recall this result was published separately in a mathematical journal but cant find the reference right now.

a more recent/advanced topic is detecting polymorphic viruses that change their code in equivalent but random ways.

another promising approach that seems to avoid the halting problem issue (in a way that demonstrates abstract theoretical "no-go theorems" can be misleading or even inapplicable in practice) is to create a secure "sandbox" in which a program can run but cannot do anything harmful.

the modern web browser can be seen as an attempt to build such a system. the complexity of securing it arises mainly with Javascript.

Google is building the NaCL[3] framework that partly originated in academia and is the current leading contender for a high functional sandbox system integrated into the modern browser that still allows machine code. a provably secure software checker validates candidate programs. there are recent dramatic improvements announced[4].

a novel recent idea is to use graph based analysis of execution traces[5].

a more recent topic of virtualization has various security implications/applications as you note eg virus vendors building virtualization systems to find/detect viruses etc.[6]

the sophistication of the recent stuxnet virus, apparently the worlds 1st state/govt-sponsored, military-agency-developed virus for cyber/espionage/sabotage purposes, has led to serious/heavy academic study, see the extensive references on wikipedia. there is a recent/new variant discovered targeting the financial industry called flame.

[2] Trends in computer virus research Cohen, 1991

[3] Native Client: A Sandbox for Portable, Untrusted x86 Native Code by Yee et al 2009

[5] Graph-based malware detection using dynamic analysis by Anderson et al

[6] Detection of Metamorphic and Virtualization-based Malware using Algebraic Specification by Webster, Malcolm

• addendum, heres another cool ref from 2003 in IEEE on the slammer virus by moore et al, possibly the fastest spreading virus in the history of all malware. some other scientific studies/papers on it also.
– vzn
Aug 17, 2012 at 2:07