Archive for Discrete Mathematics

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!)

Advertisements

Leave a Comment

Combinatoric Input Set Generation

GeneratorI’ve been studying combinatoric methods of generating test cases for quite some time now. Most publicly available fuzz testing packages implement fairly crude techniques for passing input values to applications–although recent research is becoming more creative in attacking the issue because of insufficient path coverage metrics by orthodox methods. Generating input sets combinatorially is a much more holistic approach to the black-box software testing paradigm.

In this article, I’ll be providing a brief overview of how set operations taken from the field of discrete mathematics can be applied to fuzz testing. Explicit definitions of set operations can be found elsewhere and links to Wikipedia are provided where appropriate. Brief explanations on set theory will be given here but I will mainly be focusing on how it relates to software testing.

Let’s start off with permutations; just about any computer science bachelor is familiar with these. They’re the possible orderings of a sequence. A “sequence” may consist of members that are non-unique (which is in contrast to a “set” whose members are unordered and unique.) For example, the permutations of sequence {1,2,3} are:

{{1,2,3},{1,3,2}, {2,1,3},{2,3,1},{3,1,2},{3,2,1}}

Easy enough. Permutations can be used when testing protocols where the order of commands is significant. For example, if testing the FTP protocol with a sequence of {“STAT .”,”CWD ..”,”MKD foo”} depending on the order in which the commands are executed, the client could be retrieving the status for and/or making the “foo” directory in the parent/child directories.

Sets of subsets (also known as combinations) are also quite useful and are expressed using what’s called “n-choose-r” notation because r elements are being chosen from a set that has n elements in total (the set is said to have cardinality n.) Combinations can be utilized to enumerate command-line argument possibilities since the order of argv values is usually irrelevant. Say an executable has the command line flags “-n”, “-i”, “-q”, and “-v”. We want to generate all subsets of cardinality 2 (4-choose-2.) The answer is:

{{“-n”,”-i”},{“-n”,”-q”},{“-n”,”-v”},{“-i”,”-q”},

{“-i”,”-v”},{“-q”,”-v”}}

r-permutations are similar to subsets in that a given amount of objects are chosen from the list but since permutations are represented as sequences the order of the elements matters. Using the same baseline sequence as the previously described n-permutations, the 2-permutations of {1,2,3} are as follows:

{{1,2},{2,1},{1,3},{3,1},{2,3},{3,2}}

Again, observe how these permutations would affect the logic of network protocol commands processed by a server daemon..

Moving on, a power set is the set of all subsets including the empty set. Using the example above, the power set of {“-n”,”-i”,”-q”,”-v”} looks like this:

{{},{“-n”},{“-i”},{“-q”},{“-v”},{“-n”,”-i”},{“-n”,”-q”},

{“-n”,”-v”},{“-i”,”-q”}{“-i”,”-v”},{“-q”,”-v”},

{“-n”,”-i”,”-q”},{“-n”,”-q”,”-v”},{“-n”,”-i”,”-v”},

{“-i”,”-q”,”-v”},{“-n”,”-i”,”-q”,”-v”}}

The accuracy of the power set calculation can be checked because power sets have a cardinality of 2**n. In this case, 2**4=16. Other set operations can be checked with similar formulas.

Taking it another step further, consider giving that executable whose command line flags are being generated environment variable input as well. Suppose that the power set for the command line options is:

{{},{“-n”},{“-i”},{“-n”,”-i”}}

and the power set for the environment variable values is:

{{},{“TERM=vt100”},{“TERM=%n%n%n”}},{“LOGIN=root”},

{“LOGIN=%n%n%n”},{“TERM=vt100″,”LOGIN=root”},

{“TERM=%n%n%n”,”LOGIN=root”},

{“TERM=%n%n%n”,”LOGIN=%n%n%n”}}

The environment variable names and values were paired up using a set operation known as the Cartesian product. i.e. the Cartesian product of the sets {{“TERM”}} and {“vt100″,”%n%n%n”} is:

{{“TERM”,”vt100″},{“TERM”,”%n%n%n”}}

Taking further advantage of Cartesian products, all possible pairings of command line flags and environment values are generated. I won’t be typing the whole thing out here as it is excruciatingly long but it would start out something like this:

{{{},{}},{{},”TERM=vt100″},{{},”TERM=%n%n%n”}},

{{},”LOGIN=root”}, … , {{“-n”,”-i”},{“TERM=%n%n%n”,”LOGIN=root”}},

{{“-n”,”-i”},{{“TERM=%n%n%n”,”LOGIN=%n%n%n”}}}

I put the ellipsis in there because, well, you get the idea! This continues on until all possible subsets of command line flags have been paired with all possible subsets of pairings of environment variable names and values. The final Cartesian product for two power sets of equal size can be represented visually by Pascal’s triangle.

The aforementioned set operations can be used to systematically prove the correctness of simple computer programs via deterministic testing. Modern computer programs are so complex that attempting to calculate all possible input scenarios would be infeasible with a silicon-based machine. In the future, I expect that it will be commonplace for quantum molecular systems or perhaps even DNA computers to solve software assurance problems (and many others) in constant time or O(1), but I digress.

Since silicon will be prevalent for the foreseeable future, the input space used for a real-world software test has to be reduced. The goal is to minimize test executions while maximizing path coverage so disparate input sets must be chosen. This is where “pseudo exhaustive”, “n-way”, or more recently “6-way” testing comes into practice. More information about input space reduction and pseudo exhaustive testing is in Rick Kuhn’s research at NIST.

Leave a Comment

%d bloggers like this: