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?
