<p>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).</p>

<p>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!</p>

<ul>
<li>Ambler, A. P. and Barrow, H. G. and Brown, C. M. and Burstall, R. M. and Popplestone, R. J., <em>A versatile system for computer-controlled assembly</em>, Artificial Intelligence <strong>6</strong> 129–156, 1975. doi: <a href="http://dx.doi.org/10.1016/0004-3702%2875%2990006-5" rel="nofollow">10.1016/0004-3702(75)90006-5</a></li>
</ul>

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

<p>One way to express the optimization problem is as follows.</p>

<blockquote>
  <p>MAXIMUM PARTIAL CSP:<br>
  <em>Input:</em> CSP instance<br>
  <em>Output:</em> prop $f$<br>
  <em>Criterion:</em> maximize $|f|$</p>
</blockquote>

<p>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.</p>

<p>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$).</p>

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

<hr>

<p>Footnote: The term <em>prop</em> 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 <em>nogood</em>, 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.</p>

<ul>
<li>Stallman, Richard M. and Sussman, Gerald Jay, <em>Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis</em>, MIT Artificial Intelligence Laboratory Memo No. 380, 1976. (<a href="http://hdl.handle.net/1721.1/6255" rel="nofollow">PDF</a>)</li>
</ul>

CC BY-SA 2.5
2010-10-06T22:02:10.683Z
2010-10-07T21:19:21.560Z
2010-10-07T21:19:21.560Z
András Salamon
<p>The following question has come up a number of times when <em>testing</em> the security of a system or model. </p>

<p><strong>Motivation:</strong> 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 <a href="http://en.wikipedia.org/wiki/Fuzz_testing"><em>fuzzing</em></a> 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.</p>

<p>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. </p>

<p>I'm looking for work describing the following notions:</p>

<ul>
<li><p>The <a href="http://en.wikipedia.org/wiki/Penumbra"><em>penumbra</em></a> of $M$ is a set $M'\subseteq \mathcal{M}$ such that for each 
$m\in M'$ $m\not\models\Phi$ <em>and</em> in some sense the elements of $M'$ are <em>close to</em> the elements of $M$. One can think of the <em>penumbra</em> as the <em>almost solutions</em>. Of course, this notion will not be unique.</p></li>
<li><p>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$.</p></li>
</ul>

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

<p>I found inspiration in 
<a href="http://en.wikipedia.org/wiki/Mathematical_morphology">mathematical morphology</a>, hence my visual metaphor, but the two worlds are parsecs apart. Is there any useful work there? Or perhaps in the world of <a href="http://en.wikipedia.org/wiki/Rough_set">rough sets</a>?</p>

<p>Can anyone shed light?</p>

CC BY-SA 2.5
2010-10-06T13:56:42.867Z
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
CC BY-SA 2.5
2010-10-06T15:48:01.780Z
That is indeed true. I'm alluding the the approach known as fuzzing.
Dave Clarke
CC BY-SA 2.5
2010-10-07T11:17:27.817Z
By the way, CSP = Constraint Satisfaction Problem.
Sadeq Dousti
<lo.logic><csp><security>
Finding the penumbra of a Constraint Satisfaction Problem
Dave Clarke
# Finding the penumbra of a Constraint Satisfaction Problem

(Asked by: username_0 on 2010-10-06)

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*](http://en.wikipedia.org/wiki/Fuzz_testing) 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*](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Rough_set)?

Can anyone shed light?

**Tags:** lo.logic, csp, security
> **Comments:**
> **username_1**: 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.  
> **username_0**: That is indeed true. I'm alluding the the approach known as fuzzing.  
> **username_2**: By the way, CSP = Constraint Satisfaction Problem.  

---

## 1 answers

### Answer by username_3 on 2010-10-06. Score: 6

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](http://dx.doi.org/10.1016/0004-3702%2875%2990006-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](http://hdl.handle.net/1721.1/6255))


---

