Finding the penumbra of a Constraint Satisfaction Problem

The following question has come up a number of times when testing the security of a system or model.

Motivation: Software security flaws often come not from bugs due to valid inputs, but bugs resulting from invalid inputs that are sufficiently close to valid inputs to get past many of the straightforward validity checks. The classic example is of course buffer overflows, where the input is reasonable, except that it is too large. Compilers and other tools can help address these problems by modifying the layout of the stack and heap and by other obfuscation techniques. An alternative is to remove the problems from the source code itself. One technique called fuzzing bombards the program with inputs are close to expected inputs, but are in some places unreasonable (large values for integer or string fields). I would like to understand fuzzing (as one example) from a more formal perspective.

Assume that the space of valid inputs is described by constraints $\Phi$. Let $M$ be the set of solutions of such constraints, namely $M=\lbrace m\in\mathcal{M}~|~m\models\Phi\rbrace$, where $\mathcal{M}$ is the space of possible inputs.

I'm looking for work describing the following notions:

• The penumbra of $M$ is a set $M'\subseteq \mathcal{M}$ such that for each $m\in M'$ $m\not\models\Phi$ and in some sense the elements of $M'$ are close to the elements of $M$. One can think of the penumbra as the almost solutions. Of course, this notion will not be unique.

• Ways of relaxing the constraints $\Phi$ to $\Phi'$ such that firstly $\Phi\Rightarrow\Phi'$ and $\Phi'\land\neg\Phi$ is, in a sense, the syntactic penumbra of $\Phi$.

"Penumbra" is a word I selected to describe the concept. It may well be called something else.

I found inspiration in mathematical morphology, hence my visual metaphor, but the two worlds are parsecs apart. Is there any useful work there? Or perhaps in the world of rough sets?

Can anyone shed light?

• The problem is by itself really interesting, however most of the time the interest in not in constructing the penumbra (I am not aware of a more "official" name) but rather in obfuscating techniques that avoid software tampering attacks (such as attacks through modification of the input). This techniques hide the core of the behavior of the program by flooding it with something else. For instance, you can build a program by interleaving the original one together with a program that hardcode the resolution of a NP hard problem on a specific instance. – Sylvain Peyronnet Oct 6 '10 at 13:56
• That is indeed true. I'm alluding the the approach known as fuzzing. – Dave Clarke Oct 6 '10 at 15:48
• By the way, CSP = Constraint Satisfaction Problem. – M.S. Dousti Oct 7 '10 at 11:17

Much of the attention paid to optimization variants of the constraint satisfaction problem (CSP) has focused on satisfying some number of constraints (MAX-CSP), or in the Boolean case on picking the solution which assigns as many variables as possible the value 1 (MAX-ONES, there is also MIN-ONES).

Instead, you are asking about a variant that could be called MAXIMUM PARTIAL CSP. This was studied at least as far back as the late 1960s, but I'm not aware of it having an established name. It is a natural problem, and it would be good to see more work investigating it. Thank you for providing another potential application for this problem!

• Ambler, A. P. and Barrow, H. G. and Brown, C. M. and Burstall, R. M. and Popplestone, R. J., A versatile system for computer-controlled assembly, Artificial Intelligence 6 129–156, 1975. doi: 10.1016/0004-3702(75)90006-5

A set of variable-value assignments is called a partial assignment. One can write a variable-value assignment as a (variable, value) tuple. Partial assignments are then simply functions from variables to values. Props are partial assignments that don't violate any constraint. Equivalently, a prop contains no partial assignment forbidden by some constraint (as a subset).

One way to express the optimization problem is as follows.

MAXIMUM PARTIAL CSP:
Input: CSP instance
Output: prop $f$
Criterion: maximize $|f|$

In an instance with $n$ variables, clearly a prop of cardinality $n$ will be a solution. There may exist large props, with cardinality up to $n-1$, that are not contained in any solution.

In the terminology you propose, the set of props with maximum cardinality $k$ forms the penumbra, perhaps even with some additional leeway $d$ (so cardinality at least $k-d$).

The second part of your question also appears highly interesting, but I am not aware of any work related to it.

Footnote: The term prop is from my thesis; it is meant to convey the idea that such partial assignments are proper, and also that they support the set of solutions. This is in contrast to a nogood, which is the accepted term to describe a partial assignment that cannot be extended to a solution. The word "nogood" was introduced by Richard Stallman and Gerald Sussman in 1976, when RMS was still an AI researcher instead of software freedom activist.

• Stallman, Richard M. and Sussman, Gerald Jay, Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis, MIT Artificial Intelligence Laboratory Memo No. 380, 1976. (PDF)