<p><a href="http://en.wikipedia.org/wiki/Fred_Cohen" rel="nofollow">Fred Cohen</a> is an authority &amp; 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. </p>

<p>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. </p>

<p>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".</p>

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

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

<p>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.</p>

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

<p>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].</p>

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

<p>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]</p>

<p>the sophistication of the recent <a href="http://en.wikipedia.org/wiki/Stuxnet" rel="nofollow">stuxnet virus</a>, 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 <a href="http://en.wikipedia.org/wiki/Flame_%28malware%29" rel="nofollow">flame</a>.</p>

<p>[1] <a href="http://www.research.ibm.com/antivirus/SciPapers/VB2000DC.htm" rel="nofollow">An Undetectable Computer Virus David M. Chess and Steve R. White</a></p>

<p>[2] <a href="http://all.net/books/tech/japan.pdf" rel="nofollow">Trends in computer virus research</a> Cohen, 1991</p>

<p>[3] <a href="http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/34913.pdf" rel="nofollow">Native Client: A Sandbox for Portable, Untrusted x86 Native Code</a> by Yee et al 2009</p>

<p>[4] <a href="http://phys.org/news/2012-07-nacl-rocksalt-scientists-tool-software.html" rel="nofollow">NaCl to give way to RockSalt: Computer scientists develop a tool to improve software fault isolation</a> 2012</p>

<p>[5] <a href="http://www.stat.lanl.gov/staff/CurtStorlie/malware_JCV.pdf" rel="nofollow">Graph-based malware detection using dynamic analysis</a> by Anderson et al</p>

<p>[6] <a href="http://www.csc.liv.ac.uk/~grant/PS/eicar.pdf" rel="nofollow">Detection of Metamorphic and Virtualization-based
Malware using Algebraic Specification</a> by Webster, Malcolm</p>

CC BY-SA 3.0
2012-08-17T02:07:18.537Z
addendum, heres another cool ref from 2003 in IEEE [on the slammer virus by moore et al](http://cseweb.ucsd.edu/~savage/papers/IEEESP03.pdf), possibly the fastest spreading virus in the history of all malware. some other scientific studies/papers on it also.
vzn
CC BY-SA 3.0
2012-08-10T18:54:38.687Z
2012-08-10T18:54:38.687Z
vzn
<p>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. </p>

<p>I found a very useful <a href="http://www.youtube.com/watch?v=k4Ry1trQhDk">talk</a> (BlackHat 2010) by Greg Hoglund on <code>Malware attribution</code> 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.</p>

<p>I have two questions:</p>

<ol>
<li>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.  </li>
<li>As I am not strong in TCS, I would like to know where exactly TCS fits
in malware research.</li>
</ol>

<p>Thank you.</p>

CC BY-SA 3.0
2012-08-10T01:41:27.677Z
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
CC BY-SA 3.0
2012-08-10T06:14:01.800Z
Look up semantics based approaches to malware detection for approaches with more theory.
Vijay D
CC BY-SA 3.0
2012-08-10T08:24:21.080Z
You might be interested in the question [What is the branch of Computer Science that studies how Anti Virus programs work?](http://cs.stackexchange.com/questions/2130/what-is-the-branch-of-computer-science-that-studies-how-anti-virus-programs-work/) on CS.SE.
Juho
CC BY-SA 3.0
2012-08-10T21:13:39.747Z
There's a book called "Malicious Cryptography" with ideas on how TCS can be used in malware.
sdcvvc
<cr.crypto-security><security>
Appilicability of Theoritical Computer Science in Malware research
Maggie
# Appilicability of Theoritical Computer Science in Malware research

(Asked by: username_0 on 2012-08-10)

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](http://www.youtube.com/watch?v=k4Ry1trQhDk) (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.

**Tags:** cr.crypto-security, security

> **Comments:**
> **username_1**: 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  
> **username_2**: Look up semantics based approaches to malware detection for approaches with more theory.  
> **username_3**: You might be interested in the question [What is the branch of Computer Science that studies how Anti Virus programs work?](http://cs.stackexchange.com/questions/2130/what-is-the-branch-of-computer-science-that-studies-how-anti-virus-programs-work/) on CS.SE.  
> **username_4**: There's a book called "Malicious Cryptography" with ideas on how TCS can be used in malware.  

---

## 1 answers

### Answer by username_1 on 2012-08-10. Score: 1

[Fred Cohen](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Stuxnet), 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](http://en.wikipedia.org/wiki/Flame_%28malware%29).

[1] [An Undetectable Computer Virus David M. Chess and Steve R. White](http://www.research.ibm.com/antivirus/SciPapers/VB2000DC.htm)

[2] [Trends in computer virus research](http://all.net/books/tech/japan.pdf) Cohen, 1991

[3] [Native Client: A Sandbox for Portable, Untrusted x86 Native Code](http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/34913.pdf) by Yee et al 2009

[4] [NaCl to give way to RockSalt: Computer scientists develop a tool to improve software fault isolation](http://phys.org/news/2012-07-nacl-rocksalt-scientists-tool-software.html) 2012

[5] [Graph-based malware detection using dynamic analysis](http://www.stat.lanl.gov/staff/CurtStorlie/malware_JCV.pdf) by Anderson et al

[6] [Detection of Metamorphic and Virtualization-based
Malware using Algebraic Specification](http://www.csc.liv.ac.uk/~grant/PS/eicar.pdf) by Webster, Malcolm

> **Comments:**
> **username_1**: addendum, heres another cool ref from 2003 in IEEE [on the slammer virus by moore et al](http://cseweb.ucsd.edu/~savage/papers/IEEESP03.pdf), possibly the fastest spreading virus in the history of all malware. some other scientific studies/papers on it also.  

---

