Tool Kills Hidden Linux Bugs, Vulnerabilities

mask.of.sanity writes with this excerpt from SC Magazine: "Australian researcher Silvio Cesare has released a tool capable of automatically detecting bugs and vulnerabilities in embedded Linux libraries. The script correlates vulnerability advisory CVEs for third-party libraries to determine if holes have carried over to Linux platforms or have not been patched. Such holes often escape the eye of developers because the libraries may not be kept updated with sources. This is further compounded because vulnerabilities in cross distributed packages can leave Linux platforms vulnerable."

Comments

And they're going to call the tool...

[Anonymous Coward]

"Regression Testing"

90% false positives?!

[Cyko_01]

sounds like he needs to run it on his own code

Re:90% false positives?!

[Anonymous Coward]

Since his tool looks for vulnerabilities and not "bugs" (if you want to call them that), it would be pointless to run the tool on itself with the aim of reducing false positives.

Also, to put that statement in context:

"While about 90 per cent of vulnerabilities produced by the tool were false-positives, Cesare said vetting the results takes seconds and was considerably faster than using manual processes."

That sounds like a worthwhile improvement, no?

Re:90% false positives?!

[Anonymous Coward]

I think what the grandparent meant is that a tool which reports 90% noise is a tool that people don't use.

Re:90% false positives?!

[arkenian]

My understanding is that most of the IA "scanning" tools out there have very high "false positive" rates, but that's because they're really designed to eliminate all "known good" and present anything slightly questionable to the user, as an alternative to purely manual review. So a 90% FP rate is not necessarily something that would prevent people from using the tool.

Re:Automatically detect bugs and vulnerabilities??

[jensend]

You probably already know this, but Rice's Theorem etc only apply to supposed decision procedures. It's quite possible to write a program which will often recognize that other programs have some nontrivial semantic property (halting, having a particular kind of bug, etc) and will decide correctly on a broad class of real-world programs. You just can't write one which will always give you a yes or no answer in finite time and always be right.

Re:Automatically detect bugs and vulnerabilities??

[seandiggity]

Theoretically you can. All physical machines are finite state machines, so you can enumerate all configurations (and hence, all bugs) in finite time.

...but you can't write a *general algorithm* to do that.

Re:security circus

[wdef]

You're talking about snake oil tools from commercial interests. This tool doesn't detect bugs. It just looks for code similar to that of documented vulnerabilities from what I read. This cuts down the laborious business of trying to vetting code against thousands of advisories and reduces this to a list of possible matches. It doesn't remove the need for a real engineer to go over that list and check for false positives. But it's a huge improvement.

Forbidding embedded libraries is common on distros

[Anonymous Coward]

At least Debian and Fedora, and likely every other non-shitty Linux distro *strongly* object to packages with embedded libraries, for exactly this reason: it is *unsanitary* and *dangerous*: it breaks the flow of security and regular bug fixes, and it greatly increases the exposure of users to both bugs and security holes.

It gets so bad that Debian has a standing bad blood with the Ruby community because Ruby is "embedded third-party library hell", and therefore Debian maintainers either considers Ruby stuff unpackageable, or have to get in fights with upstream because they unbundle the libraries and suddenly upstream actually has to do its job and make sure their stuff works with more recent versions of the third-party libraries... (when it is an older version, that's a Debian bug).

If you got games from the Humble Bundle 1 and 2, you likely know that *for up-to-date latest stable Debian, Ubuntu, Fedora...*, many of the SDL bugs related to sound and video are fixed by removing the libraries duplicated in the game tarball, so as to use the ones shipped by the distro...

Re:Uh, yes.

[dkf]

The poster actually provided one. "Enumerate all configurations". Start in every possible start state, run the program and stop once the machine reaches a previously seen state (that'll be an infinite loop, so the machine will never halt given that program and input), or halts. Since the machine can only have a fixed number of states (finite size) either of those two things will within at most N steps, where N is some fixed (probably very very large) number.

Of course if you actually had a machine large enough (enough memory, CPU, etc.) to do that, you'd want to use that to actually run your program...

Won't work.

1. You underestimate just how much state will be required. Really. I've written code to do this sort of detection in the past (where the subject program was provably finite and small) and it took gigabytes of memory to tackle programs with only a few bits-worth of real state. (You can do better by working with a model of the program, but then you've got problems ensuring that the model actually correlates with reality.) Heck, I even found that Google's indexed the papers that I wrote on this and had published 14 years ago.
2. It's provably impossible to solve in general, since you could use the solution to create a program that only stops if it doesn't and vice versa, which is pure nonsense. Moreover, if you could solve it you could also solve a whole range of advanced mathematical conjectures, as you just use the subject program to encode the search through possible solutions. The general halting problem turns out to trivially encompass just about the whole of mathematics!

You can get tractable solutions using a ternary logic though: algorithms that say "I don't know" some of the time are eminently practical.