Posts Tagged bugs

Jenny’s Got a Perfect Pair of..

binomial coefficients

binomial coefficients

..binomial coefficients?! That’s right. I’ve found the web site of a Mr. Bob Jenkins with an entire page dedicated to a pairwise covering array generator named jenny.c. I’m fairly sure that only the most hardcore of the software testing weenies have some notion of what those are so for the sake of being succinct I’ll be providing my own explanation here: A pairwise covering array generator is a program for silicon computing machines that deduces sequences of input value possibilities for the purposes of software testing; and yes, I did say silicon computers–since testing their software is really a question of the great Mr. Turing’s halting problem, the existence of a practical, affordable, and efficient nano/molecular computing device such as a DNA computer, Feynman machine, universal quantum computer, etc. would essentially predicate a swift solution to the problem of testing contemporary computer software in non-deterministic polynomial time. The only problem we would have then is how to test those fantastic, futuristic, (seemingly science fictive) yet wondrous problem-solving inventions as they break through laborious barriers of algorithmic complexities that twentieth century computer scientists could have only dreamed about: PCP, #P, PSPACE-complete, 2-EXPTIME and beyond.. The stuff that dreams are made of.

Now, let’s return to Earth and learn about a few things that make Jenny so special. Computer scientists learned early on in their studies of software testing that pairwise or test cases with two input values were the most likely to uncover erroneous programming or “bugs.” Forget the luxury of automation for a minute, old school programmers typed input pairs manually to test their own software. Code tested in that manner was most likely some sort of special-purpose console mode utility. (Celsius to Fahrenheit, anyone?) As the computing power of the desktop PC increased according to Moore’s law, it became time-effective to write a simple program to generate these input pairs instead of toiling over it yourself–I suppose not testing at all was another option. Today, still some software is released to market after only very minor functional and/or quality assurance testing. Regression, stress, security, and other forms of testing cost money and reduce time to market, but in reality significant return on investment acts as a hedge against any losses incurred. Even ephemeral losses justify the absolute necessity of these expenditures.

A Jenny built in modern times undoubtedly has the power to deductively prove that a software product of the eighties decade is comprised of components (or units) that are fundamentally error-free. However, the paradox remains that improvements in automated software testers share a linear relationship with improvements of software in general. Thus, pairwise has become “n-way” which describes the process of utilizing greater multiples of input values in order to cover acceptable numbers of test cases. The number of covering arrays generated in this fashion grows exponentially and can be calculated as a binomial coefficient (see formula below.)

(n choose r) in factorial terms

(n choose r) in factorial terms

According to Paul Black, former SAMATE (Software Assurance Metrics and Tool Evaluation) project leader, researchers at NIST have pegged 6-way as the magic number for optimal fault interaction coverage (notably Rick Kuhn and Dolores Wallace.) This conclusion is based on hard evidence from studies on real-world software scenarios including medical devices and the aerospace industry. However, it would not surprise me to see this approximation rise significantly in the coming decades, just as the paradoxical relationship between general-purpose software and automated software testing programs shifts itself in accordance with Moore’s law. If not by Moore, then by some other axiom of metric progression such as Rogers’ bell curve of technological adoption.

I’ve also got a hunch that the tiny percentage of bugs in that “n is arbitrarily greater than 6” range are some of the most critical, powerfully impacting software vulnerabilities known to man. They lie on an attack surface that’s almost non-existent; this makes them by definition, obscure, non-obvious, shadowy, and hidden. Vulnerabilities in this category are the most important by their very nature. Therefore, detecting vulnerabilities of this type will involve people and tools that are masters of marksmanship and artistic in their innovation. Research in this area is entering a steadfast beginning especially within the realms of dynamic instrumentation or binary steering, active analysis, fault propagation, higher-order preconditions/dependencies, concurrency issues, race conditions, etc. I believe that combining merits inherent in various analysis techniques will lead to perfection in software testing.

For perfection in hashing, check out GNU’s gperf, read how Bob used a perfect hashing technique to augment Jenny’s n-tuples; then get ready for our Big ßeta release of the BlockWatch client software (just in time for the holiday season!)

Leave a Comment

Ignorance is Bliss

Ignorance is Bliss When you think about it, time really is all we have. It’s what you have at your disposal, to do anything and everything. It seems that we’re better off not knowing when it comes to security–for our own good. Can it really be so utilitarian?

To anybody out there writing exploits: make sure you’re doing it just for fun. Currently, there are no outlets for any financial gain that will accurately measure your time investment or fairly compensate your hard work.

Security Objectives’ own Shane Macaulay “owned” Vista SP1 in the PWN2OWN contest at CanSecWest 2008 by exploiting a bug in Adobe Flash. As a result of the contest’s categorization of the bug as third-party, the exploit was grossly under-appraised (especially when considering cross-platform targets and the fact that it would work well into the future with Vista’s new Service Pack.) Sure, it technically was a bug in a third-party application, but this particular third-party application happens to be installed on just about every Internet-enabled PC. According to Adobe, “Adobe® Flash® Player is the world’s most pervasive software platform, used by over 2 million professionals and reaching over 98% of Internet-enabled desktops in mature markets as well as a wide range of devices.”

Even if Shane was unfairly compensated, it doesn’t matter because at least he used “responsible disclosure” — or does it? I highly doubt that the people in charge of the companies writing buggy software and brokering bug information have any idea about the amount of work and skill that goes into discovering an exploitable bug, let alone writing a proof-of-concept for it. As it stands, software companies are setting themselves up for a black market in digital weapons trading of unprecedented proportions.

Here’s something else to think about.. I expect Adobe to patch this one rather quickly given all the publicity. How long does it take for a vendor to fix a given vulnerability when it is reported to them directly? Even some of the brokered “upcoming advisories” on 3Com’s ZDI site are many months or even years stale. This “patchtile dysfunction” will increase the value of a 0-day exploit exponentially.

Time is money and to make up for lost time, Mr. Macaulay decided to sell the laptop he had won on eBay. An innocent bystander at the contest dubbed this decision “from pwn to pawn.” So why not? Laptops get sold on eBay everyday–but not this one. It wasn’t long before eBay pulled Mr. Macaulay’s item from auction on the first of April, ostensibly as an April Fool’s shenanigan. This came as a surprise to me. Things to consider here:

  • The laptop may or may not have had forensic evidence of the controlled attack that occurred during the contest.
  • Even so, Mr. Macaulay is a responsible discloser and would not have shipped the laptop until the bug was patched.
  • Mr. Macaulay’s and Mr. Sotirov’s autographs should have increased the laptop value, regardless.

This incident, in a way, reminded me of eBay’s great fearwall debacle from a few years ago (CVE-2005-4131.) In that case, there were several key differences: an information broker such as ZDI was not involved, a pseudonym was being used, the code statements where the memory corruption occurred were disclosed, and no computer hardware was for sale. Nevertheless, I respect eBay’s decision to discontinue the auction as this is obviously a very controversial issue.

Brokering information? How can you do it? From experience, the idea of using an escrow service and 3rd party verification is largely ineffective. It would appear that ZDI is the only show in town. Of course there’s that auction service, but you have to send them your exploit first so how does that work? It appears that they’re still trying to do business by the way, despite alleged legal troubles. I’m subscribed to their mailing list and they send out an e-mail every time new information goes up for auction; they put up a dozen or so new exploits last week but it would appear that few if any were sold. Where do we go from here? Is brokering information even possible?

Imagine for a moment a scenario where a dozen or so exploits of critical severity related to a single software company are posted to Full Disclosure with rumors of many more circulating in the underground and exploits actively being carried out in the wild. Now imagine shareholders shorting that company’s stock. I suppose that the vulnerability information might be more realistically valued in a situation such as this. Anyone have any other ideas?

Comments (1)

%d bloggers like this: