About unavoidable false positive

[Chengnian Sun]

Hi,

I found that there would be unavoidable false positive.

Can someone give me a hint? I cannot figure out such a situation now.

Thanks.


--
Best Regards.

Chengnian SUN.

[George Candea]

Are you asking for a scenario in which false positives could occur in Dimmunix?

If yes, then you can find examples and more information in section 5.5 of

http://www.usenix.org/events/osdi08/tech/full_papers/jula/jula_html/index.html

If not, then please explain a little further what information you are looking for.

Cheers,

George

[Chengnian Sun]

Thanks for your reply.

 

I understand there can be false positives in Dimmunix. For example, if the matching depth is set to 1, it will be easier for signatures to be matched.

 

In the paper, there is some descriptions "False positives are not exclusively due to overly general matching, but could also be caused by input or value dependencies; e.g., pattern may lead to deadlock for some inputs but not for others, so avoiding can have false positives even at the most precise matching depth. For this reason, can be non-zero, and multiple depths can have the same rate; choosing the smallest depth gives us the most general pattern."

 

In fact, I am curious about an example program and a deadlock pattern of this type "pattern may lead to deadlock for some inputs but not for others, so avoiding can have false positives even at the most precise matching depth".

Thanks.

 

Chengnian.

[George Candea]

Ah, I see. Well, here is an example that could result in input-dependent FPs:

 1: func( mutex A, mutex B ) {

 2:   lock( A );

 3:   lock( B );

 4:   ...

 5:   unlock( B );

 6:   unlock( A );

 7: }
 8:

 9: main () {

10:   read i and j from user

11:   start thread T1 and (in T1) call func(Li,Lj)

12:   read p and q from user

13:   start thread T2 and (in T2) call func(Lp,Lq)

14: }

If the user gives you i=q=1, j=p=2, then the program could deadlock, because you have one thread calling func(L1,L2) and another thread calling func(L2,L1). Dimmunix will save the corresponding signature, along the lines of { [main:11,func:2], [main:13,func:2] }.

If later on the user gives you i=1, j=2, p=3, q=4, then the program has no way to deadlock, yet Dimmunix still avoids the deadlock pattern. There is nothing incorrect about this, but it reduces the level of concurrency in the execution, which may reduce performance.

Admittedly, this is a contrived example, but it is theoretically possible. We have never seen it occur in practice, so we didn't worry much about it.

- George

[Chengnian Sun]

Great. That is the example I want.

 

Thanks so much.

 

Chengnian.