Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question

closed as off topic by Peter Shor , Lev Reyzin, Suresh Venkat Feb 11 '11 at 7:30

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

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 meta.cstheory.stackexchange.com/questions/514/… –  Suresh Venkat Jan 10 '11 at 17:13
@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 Jan 10 '11 at 17:18
@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 Jan 10 '11 at 18:03
@Sadeq Scott Aaronson, in his answer to the meta.cstheory question linked above. –  Suresh Venkat Jan 10 '11 at 22:46
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 Jan 11 '11 at 7:44
show 7 more comments

1 Answer

up vote 4 down vote accepted

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. While this term is usually applied to IDS algorithms, there's nothing preventing you from applying it to antivirus algorithms.

share|improve this answer
Sadeq, I think this question is out of scope as currently stated. –  Suresh Venkat Jan 10 '11 at 17:15
@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 Jan 10 '11 at 17:20
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.