<p>First of all, I warn that things aren't that simple. Up until now, researchers haven't came up with a perfect algorithm to do that (and I'm almost sure they never will!)</p>

<p>However, there are many competing approaches to do what you want. They compete in efficiency, false-positive rate, false-negative rate, and so on.</p>

<p>The model is as follows: Assume you have a number of algorithms (fuzzy, genetic, neural net, etc.) which process (possibly different) streams of data, and generate alerts if they find anomaly. You then have a <strong>stream of alerts</strong>, which must be <strong>correlated</strong> by another algorithm. Unsurprisingly, such algorithm is called <strong>alert correlation</strong>.</p>

<p>You can find hundreds of papers on this subject <a href="http://scholar.google.com/scholar?hl=en&amp;safe=off&amp;q=%22alert%20correlation%22" rel="nofollow">here</a>. While this term is usually applied to IDS algorithms, there's nothing preventing you from applying it to antivirus algorithms.</p>

CC BY-SA 2.5
2011-01-10T17:15:57.837Z
Sadeq, I think this question is out of scope as currently stated.
Suresh Venkat
CC BY-SA 2.5
2011-01-10T17:20:24.987Z
@Suresh: I had some prior exposure to this topic, and I believe it's an active area of research. However, I agree that the question, as stated, is on the edge of being off-topic (but I think it can be somehow acceptable). Let's give the OP some time, and see if (s)he can improve it.
Sadeq Dousti
CC BY-SA 2.5
2011-01-10T17:14:11.620Z
2011-02-10T20:56:07.033Z
2011-02-10T20:56:07.033Z
Sadeq Dousti
<p>I think people here could guide me in solving a problem related to anomaly detection. The term anomaly here refers to some malware attack.</p>

<p>I could get information about the malware infection from more than one source. For example extracting value from two different data strututres and if the value is different it is certain that virus infection is there.</p>

<p>In order to remove the false positive cases, information is gathered from different data strutres or mechanisms. In that certain information are less trusted and certain information are more trusted.</p>

<p>I am looking for a mathematical method, that could easily handle this type of situations?</p>

<p><strong>Update 1:</strong></p>

<p>Its applied in Linux Kernel for detecting some kind of anomalies. But the problem is that if the kernel is affected you cant trust anyone. But "some" behavior can tell you that anomaly is there. But some others not </p>

<p><strong>Update 2:</strong></p>

<p>Current models mainly depends on archived copy of the system before infection and then compare it with the new state. I am looking for some other method like</p>

<p>(1) Certain variables cant be accessed by a normal module
(2) Information given by command should match
(3) Module code didn't have any <em>jmp</em> instructions often</p>

<p>In these (3) is allowed to some extent. But (1) is disallowed. The (2) should certainly match. </p>

<p>Hope now things are clear.</p>

CC BY-SA 2.5
2011-01-10T17:13:23.723Z
this is out of scope for a research-level site on theoretical computer science. If you had a specific method and wished to analyze it, or even had a more concrete and focused application, then you'd be in scope. Please see http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions
Suresh Venkat
CC BY-SA 2.5
2011-01-10T17:16:39.980Z
@Suresh: There's a lot of research going on in this field (see my answer). However, I agree that the question is stated in a very high-level manner. Maybe the OP can read the references and improve on his question.
Sadeq Dousti
CC BY-SA 2.5
2011-01-10T17:18:17.680Z
@Sadeq that's what I mean. there's a place for modelling questions, but they have to be phrased well. Scott's answer in the above question has helpful suggestions in this regard
Suresh Venkat
CC BY-SA 2.5
2011-01-10T17:27:59.650Z
@Sadeq Question edited to provide more info.Hope this is enough. Or otherwise I could add more info
user3162
CC BY-SA 2.5
2011-01-10T18:03:36.687Z
@user3162, no, this doesn't really help at all. 1. What is the precise model for what is malware 2. What are current approaches that people are trying 3. in what way are they insufficient ?
Suresh Venkat
CC BY-SA 2.5
2011-01-10T18:26:56.437Z
@user3162: I think the update is making it worth! I was hoping for something theoretical, but your case is more apt for the [superuser](http://superuser.com). @Suresh: sorry, whose "Scott"?
Sadeq Dousti
CC BY-SA 2.5
2011-01-10T22:46:59.720Z
@Sadeq  Scott Aaronson, in his answer to the meta.cstheory question linked above.
Suresh Venkat
CC BY-SA 2.5
2011-01-11T06:51:14.860Z
@Sadeq @Suresh Added more theorotical information. Hope things are clear now
user3162
CC BY-SA 2.5
2011-01-11T07:44:39.373Z
I'm sorry. this does not help at all to make it more formal. I recommend you take the time to read some of the higher-voted questions on this site to get an idea of what a good question is.
Suresh Venkat
CC BY-SA 2.5
2011-01-11T09:28:57.330Z
Lets make the situation more abstract, forget about anomaly. "We have a list of information sources. The sources are assigned different credibility. Each source generates a list of numbers that indicate if event A has occurred. Based on this information we want to return a yes/no answer to the question "has event A occurred?". What is a good algorithm for answering this question?" Is this what you are asking?
Kaveh
CC BY-SA 2.5
2011-02-11T14:04:18.137Z
Closed; the question is too unclear, and the requests for clarification have not been adequately addressed.
Peter Shor 
<cr.crypto-security><formal-modeling><data-mining>
Help needed on method to use for anomaly detection
user3162
# Help needed on method to use for anomaly detection

(Asked by: username_0 on 2011-01-10)

I think people here could guide me in solving a problem related to anomaly detection. The term anomaly here refers to some malware attack.

I could get information about the malware infection from more than one source. For example extracting value from two different data strututres and if the value is different it is certain that virus infection is there.

In order to remove the false positive cases, information is gathered from different data strutres or mechanisms. In that certain information are less trusted and certain information are more trusted.

I am looking for a mathematical method, that could easily handle this type of situations?

**Update 1:**

Its applied in Linux Kernel for detecting some kind of anomalies. But the problem is that if the kernel is affected you cant trust anyone. But "some" behavior can tell you that anomaly is there. But some others not

**Update 2:**

Current models mainly depends on archived copy of the system before infection and then compare it with the new state. I am looking for some other method like

(1) Certain variables cant be accessed by a normal module
(2) Information given by command should match
(3) Module code didn't have any *jmp* instructions often

In these (3) is allowed to some extent. But (1) is disallowed. The (2) should certainly match.

Hope now things are clear.

**Tags:** cr.crypto-security, formal-modeling, data-mining

> **Comments:**
> **username_1**: this is out of scope for a research-level site on theoretical computer science. If you had a specific method and wished to analyze it, or even had a more concrete and focused application, then you'd be in scope. Please see http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions  
> **username_2**: @Suresh: There's a lot of research going on in this field (see my answer). However, I agree that the question is stated in a very high-level manner. Maybe the OP can read the references and improve on his question.  
> **username_1**: @Sadeq that's what I mean. there's a place for modelling questions, but they have to be phrased well. Scott's answer in the above question has helpful suggestions in this regard  
> **username_0**: @Sadeq Question edited to provide more info.Hope this is enough. Or otherwise I could add more info  
> **username_1**: @username_0, no, this doesn't really help at all. 1. What is the precise model for what is malware 2. What are current approaches that people are trying 3. in what way are they insufficient ?  
> **username_2**: @username_0: I think the update is making it worth! I was hoping for something theoretical, but your case is more apt for the [superuser](http://superuser.com). @Suresh: sorry, whose "Scott"?  
> **username_1**: @Sadeq  Scott Aaronson, in his answer to the meta.cstheory question linked above.  
> **username_0**: @Sadeq @Suresh Added more theorotical information. Hope things are clear now  
> **username_1**: I'm sorry. this does not help at all to make it more formal. I recommend you take the time to read some of the higher-voted questions on this site to get an idea of what a good question is.  
> **username_3**: Lets make the situation more abstract, forget about anomaly. "We have a list of information sources. The sources are assigned different credibility. Each source generates a list of numbers that indicate if event A has occurred. Based on this information we want to return a yes/no answer to the question "has event A occurred?". What is a good algorithm for answering this question?" Is this what you are asking?  
> **username_4**: Closed; the question is too unclear, and the requests for clarification have not been adequately addressed.  

---

## 1 answers

### Answer by username_2 on 2011-01-10. Score: 4 | Accepted answer

First of all, I warn that things aren't that simple. Up until now, researchers haven't came up with a perfect algorithm to do that (and I'm almost sure they never will!)

However, there are many competing approaches to do what you want. They compete in efficiency, false-positive rate, false-negative rate, and so on.

The model is as follows: Assume you have a number of algorithms (fuzzy, genetic, neural net, etc.) which process (possibly different) streams of data, and generate alerts if they find anomaly. You then have a **stream of alerts**, which must be **correlated** by another algorithm. Unsurprisingly, such algorithm is called **alert correlation**.

You can find hundreds of papers on this subject [here](http://scholar.google.com/scholar?hl=en&safe=off&q=%22alert%20correlation%22). While this term is usually applied to IDS algorithms, there's nothing preventing you from applying it to antivirus algorithms.

> **Comments:**
> **username_1**: Sadeq, I think this question is out of scope as currently stated.  
> **username_2**: @Suresh: I had some prior exposure to this topic, and I believe it's an active area of research. However, I agree that the question, as stated, is on the edge of being off-topic (but I think it can be somehow acceptable). Let's give the OP some time, and see if (s)he can improve it.  

---

