%Kazuo Iwama %iwama@csce.kyushu-u.ac.jp %Dept of Computer Science and Communication Engineering %Kyushu University %Fukuoka 812, Japan %Tel: +81-92-641-1101 %Fax: +81-92-632-5204 %-------- \documentstyle[11pt]{article} \setlength{\textwidth}{160mm} \setlength{\textheight}{230mm} \setlength{\oddsidemargin}{0mm} \setlength{\evensidemargin}{0mm} \setlength{\topmargin}{-10mm} \setlength{\parindent}{10mm} \setlength{\parskip}{3mm} \newenvironment{indention}[1]{\par \addtolength{\leftskip}{#1} \begingroup}{\endgroup\par} \renewcommand{\thefootnote}{\fnsymbol{footnote}} \def\thesection {\arabic{section}.} \begin{document} \setlength{\baselineskip}{6mm} \bibliographystyle{jplain} \begin{center} {\LARGE\bf Test-Case Generation with Proved Securities}\\ \vspace{7mm} \setlength{\baselineskip}{5mm} Kazuo Iwama and Eiji Miyano Department of Computer Science and Communication Engineering\\ Kyushu University, Fukuoka 812, Japan \end{center} %\setlength{\baselineskip}{8.7mm} \setlength{\baselineskip}{4.5mm} \section{Research Goal}\vspace*{-3mm} The satisfiability problem (SAT) for CNF predicates is a typical example of NP-complete problems, for which a variety of algorithms and analyses of their average complexities have been reported (e.g.,\cite{iwa89,pbr85}). Those algorithms are claimed to run in polynomial average-time for fairly wide range of SAT instances. However, they do not seem to have been succeeded very well in convincing their possible users. The potential reason is that those analyses commonly involve complicated mathematics and somehow unrealistic framework of the complexity theory such as the Big-O notation. Empirical tests must have merits in this sense. Unfortunately, there have been no agreed methods of test-case generation. For example, researchers in the field of logic design commonly use a fixed bench-mark set of instances, which clearly includes such a danger that algorithms can be tuned up to those particular instances. Another common method is to generate instances as strings purely at random, which we call the {\it syntactically random generation}. This method would prevent the above cheating, but it includes other serious defects since it generates only the instances that follow a certain mathematical (truly even) distribution: In the case of SAT, by calculating several easy parameters such as the number of variables, the number of clauses and the number of literals in each clause of the generated predicate, one can guess its answer almost always correctly if he knows that the instance is syntactically random \cite{fra86}. Another problem is that we cannot know the answer of each generated instance (unless we actually solve it). That means it is hard to check the answer of the algorithm under test, which could incite serious cheating again. {\it The test-case generation with known answers} has been thus introduced in \cite{iam92}. It consists of two generators, one for yes-instances (satisfiable predicates) and the other for no-instances (unsatisfiable predicates). Now we can prepare a set $I$ of test problems in which yes-instances and no-instances can be mixed as we wish. Wrong answers possibly output by the algorithm under test are now easily detected also. {\bf Our research goal in this project is to develop such a test-case generator which is \underline{efficient} and \underline{secure}. By the efficiency we mean that the generator runs in polynomial time. As the security, we introduce two different kinds of securities, a \underline{worst-case security} and an \underline{average-case security}.} The worst-case security means how we can keep the problem's intrinsic difficulty in the generated instances, under the framework of complexity theory. Suppose, for example, that our generator for no-instances would work as follows: (i) First generate a predicate $f$ of variables $x_{1}$ to $x_{n}$ completely at random. (ii) Then output $g=f\cdot (x_{n+1}+x_{n+2})(x_{n+1}+\overline{x_{n+2}}) (\overline{x_{n+1}}+x_{n+2})(\overline{x_{n+1}}+\overline{x_{n+2}})$ as a no-instance. $g$ is clearly unsatisfiable but one can see that the set $I_{g}$ of all such $g$'s is in class P. Thus one can design a polynomial-time SAT algorithm which only works for $I_{g}\cup I_{yes}$, where $I_{yes}$ may be any (possibly perfect) set of yes-instances. The generator clearly makes the problem too easy. We shall present how to claim this kind of security for instance generators, especially in the case of generators for no-instances. The average-case security means how to generate instances under a reasonable probability distribution. Suppose that both yes-instance and no-instance generators have no problem in terms of the worst-case security, namely, both {\it can} generate every yes and no instances, respectively, with probability $>0$. However, it may happen that the yes-instance generator generates {\it almost every time} the predicates whose clauses include relatively large number of clauses compared to the no-instance generator. This clearly lacks the average-case security. Our present goal is to develop the generation system so that both generators will always generate the predicates which ``look similar''. The similarity is measured by several parameters such as the distribution of the number of literals in each clause. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Generation Algorithms} Recall that our instance generator for SAT consists of two independent generators for satisfiable predicates and unsatisfiable ones, each of which can be regarded as a generator of a particular language. The model for such a generator is not unique (see .e.g. \cite{iam92}). In this research, that is a deterministic Turing machine $G$ of the following type: $G$ takes a binary string $r\in \{ 0, 1\}^*$ as its input and outputs a CNF predicate $f(r)$. $L(G)$, called {\it the language generated by $G$}, is defined as $L(G)=\{ f(r)|r\in \{ 0, 1\}^*\}$. $G$ is said to {\it run in time} $p(n)$ if $G$ halts within $p(n)$ steps whenever its output is of length $n$. Clearly the string $r$ is used to select one of many predicates in $L(G)$ and may be created at random inside $G$ in practice. Let $I_{sat}$ and $I_{\overline{sat}}$ denote the set of all the satisfiable and unsatisfiable predicates, respectively. Here is our most basic generator for satisfiable predicates: \begin{description} \item[\hspace*{10mm}Generator] SAT-GEN: \vspace{-3mm} \item[{\it Step 1}.] A single cell $C_{ans}$ is created at random. (``at random'' means using the input string appropriately.) \vspace{-3mm} \item[{\it Step 2}.] A clause $A$ is also created at random. \vspace{-3mm} \item[{\it Step 3}.] If $A$ does not cover $C_{ans}$ then $A$ is included in the instance. Otherwise, a single literal $x'$ included in $A$ is selected at random and it is changed to its negation, i.e., $\overline{x}$ if $x'=x$ and $x$ if $x'=\overline{x}$. Such a $A'$ is also included in the instance. \vspace{-3mm} \item[{\it Step 4}.] Steps 2 and 3 are repeated until the input string has been spent. \hspace{\fill}$\Box$ \vspace{-3mm} \end{description} It is not much harder to generate unsatisfiable predicates. \begin{description} \item[\hspace*{10mm}Generator] $\overline{\mbox{SAT}}$-GEN: \vspace{-3mm} \item[{\it Step 1}.] Select a variable $x$ at random and let the predicate $f_{now}=x\overline{x}$ initially. \vspace{-3mm} \item[{\it Step 2}.] One of the following (2-1) to (2-4) is randomly chosen and executed: \vspace{-3mm} \item[\hspace*{3.2mm}({\it 2-1})] Select a clause $A$ in $f_{now}$ and select a variable $x$ both at random. $f_{now}$ is modified by splitting $A$ into $(A+x)(A+\overline{x})$. \vspace{-3mm} \item[\hspace*{3.2mm}({\it 2-2})] Select a clause $A$ in $f_{now}$ and a literal $x'$ in $A$ at random. $f_{now}$ is modified by removing $x'$ from $A$. \vspace{-3mm} \item[\hspace*{3.2mm}({\it 2-3})] Select, again randomly, a pair of clauses $A$ and $B$ in $f_{now}$ such that $A$ covers $B$ (if any). We remove the (smaller) clause $B$ from $f_{now}$. \vspace{-3mm} \item[\hspace*{3.2mm}({\it 2-4})] Construct a random clause $A$ and add $A$ into $f_{now}$. \vspace{-3mm} \item[{\it Step 3}.] Repeat Step2 until the input string runs out and halt with $f_{now}$ at that time. \hspace{\fill}$\Box$\vspace{-3mm} \end{description} {\bf Theorem 1.} (i)SAT-GEN generates $I_{sat}$ and (ii)$\overline{\mbox{SAT}}$-GEN generates $I_{\overline{sat}}$. \hspace{\fill}$\Box$ (i) is almost trivial and (ii) can be proved using the common principle, called the iterated consensus, in the field of logic design. It should be noted that SAT-GEN runs in polynomial time, but unfortunately $\overline{\mbox{SAT}}$-GEN does not. The reason is the existence of ({\it 2-3}) of Step 2, which can reduce the length of the instance under generation arbitrarily. Hence, if the number of execution of ({\it 2-3}) are limited to polynomial, it will certainly run faster, i.e., in polynomial time. Let $d(n)$ be a polynomial in $n$. \begin{description} \item[\hspace*{10mm}Generator] PRV(d(n))-GEN: Everything is the same as $\overline{\mbox{SAT}}$-GEN but Step 3 is modified. \vspace{-8mm} \item[{\it Step 3}.] Repeat Step2 but we cannot choose (2-3) if we have already chosen that $d(n)$ times. \hspace{\fill}$\Box$\vspace{-3mm} \end{description} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Worst-Case Security}\vspace*{-3mm} It is easy to see that if a language $L$ can be generated in polynomial-time then $L$ is in NP. It turns out that the converse is also true for many cases, i.e., that there are no known languages in NP which cannot be generated in polynomial time\cite{saf90}. In the case of SAT also, $I_{sat}$ is generated by polynomial-time SAT-GEN. In turn, $I_{\overline{sat}}$ is a co-NP complete languages. Then it appears to be very hard to generate $I_{\overline{sat}}$ in polynomial time since it could imply NP=co-NP. Actually, $\overline{\mbox{SAT}}$-GEN does not run in polynomial-time and as will be described below, PRV($d(n)$)-GEN cannot generate all of the unsatisfiable predicates. What would happen if a generator, say $\overline{G}$, can generate only a subset of $I_{\overline{sat}}$? As mentioned earlier, if $L({\overline{G}})$ is in P then it is not secure. To claim that $L({\overline{G}})$ is not in P, a popular way is showing that $L({\overline{G}})$ is NP-complete. However, it is still not sufficient: Consider, say the following generator $G_{0}$, as $\overline{G}$. $G_{0}$ first simulates SAT-GEN and make up a (satisfiable) predicate $f$. Then $G_{0}$ add trivial $(x_{n+1})(\overline{x_{n+1}})$ to $f$ if $f$ includes variables $x_1$ through $x_n$. Since $L(\mbox{SAT-GEN})=I_{sat}$ is NP-complete, $L(G_0)$ is clearly NP-complete also. However, we have had almost no gain in terms of the security: Suppose that a solver (a SAT-algorithm designer) knows that every test problem $g$ comes from $L(G_0)\cup I_{sat}$. Then he would only try to determine if $g$ includes two simple clauses $(x_{n+1})$ and $(\overline{x_{n+1}})$ (and all the other portion includes variables $x_1$ through $x_n$) apparently in polynomial time. Formally, such $L(G_0)$ and $I_{sat}$ are called P-separable\cite{gse88} (a polynomial-time set $S$ exists such that $L(G_0)\subseteq S\subseteq \overline{I_{sat}}=I_{\overline{sat}}$). To seek a generator $G$ such that $L(G)$ and $I_{sat}$ are not P-separable, which is apparently the next step, seems to be very hard again. From those generators we would be able to construct so-called a one-way function\cite{esy84,gle89,gse88}, which no one ever succeeded in even though NP$\neq$co-NP is assumed. It should be noted that a more naive way of achieving the security is to close $L(\overline{G})$ to $I_{\overline{sat}}$. PRV($d(n)$)-GEN has a desirable nature to this goal: {\bf Theorem 2.} There exist an infinite sequence of polynomials $d_0(n)$, $d_1(n)$, $\cdots$ such that $L(G(d_i(n)))$ is NP-hard and $L(\mbox{PRV}(d_i(n))\mbox{-GEN}) \subset L(\mbox{PRV}(d_{i+1}(n))\mbox{-GEN})$ for each $i$. \hspace{\fill}$\Box$ \noindent Thus we can make $L(\mbox{PRV}(d(n))\mbox{-GEN})$ as close to $I_{\overline{sat}}$ as we wish by taking more time for its generation. Note that if $I_{sat}$ and $L(\mbox{PRV}(d_{i}(n))\mbox{-GEN})$ are P-separable, there would exist a set $L$ such that $$\underbrace{L(\mbox{PRV}(d_{0}(n))\mbox{-GEN})\subset L(\mbox{PRV}(d_{1}(n))\mbox{-GEN})\subset \cdots } _{\mbox{NP-complete}}\subset \underbrace{L}_{\mbox{P}} \subset \underbrace{L(\mbox{PRV}(2^{O(n)})\mbox{-GEN})=L_{\overline{sat}}} _{\mbox{co-NP-complete}}$$ Such $L$ would create some kind of discontinuity in the behavior of $L(\mbox{PRV}(d(n))\mbox{-GEN})$ somewhere at $d(n)$ = a non-polynomial function. However, $L(\mbox{PRV}(d(n))\mbox{-GEN})$ seems to enlarge quite smoothly as $d(n)$ becomes faster-growing. Our conjecture is that such $L$ does not exist. \section{Average-Case Security} Recall that our present goal is make the two generator (one for satisfiable predicates and the other unsatisfiable ones) generate ``similar'' predicates always. To characterize the similarity, the following two parameters seem to be fundamental. A {\it literal distribution} is denoted by ($N(x_1), N(\overline{x_1}), \cdots , N(x_{n}), N(\overline{x_{n}})$) where $N(v)$ ($v=x_{i}$ or $\overline{x_i}$) is the number of occurrences of the literal $v$ in the generated predicate. A {\it clause distribution} is ($T(1), T(2), \cdots , T(t)$) where $T(i)$ is the number of clauses consisting of exactly $i$ literals. In what follows, we only consider $(0, 0, t, 0, \cdots )$ for the clause distribution, i.e., so-called 3-SAT. Predicates whose every clause includes exactly 3 literals are called {\it 3-predicates}. \begin{description} \item[\hspace*{10mm}Generator] 3SAT($N$)-GEN: \vspace{-3mm} \item[{\it Step 1}.] Compute the number $t$ of clauses by $t=\frac{1}{3}\sum_vN(v)$. \vspace{-3mm} \item[{\it Step 2}.] A single cell $C_{ans}=v_1+v_2+v_3+\cdots +v_i+\cdots +v_n$ is created at random. $v_i$ is $x_i$ or $\overline{x_i}$. Let $C_{ans}$ also denote the set $\{ v_1, v_2, \cdots , v_n\}$ of literals. \vspace{-3mm} \item[{\it Step 3}.] If $\sum _{v\in C_{ans}}{N(\overline{v})}\geq t$, then go to Step 5, otherwise go to Step 4. ($\overline{v}$ is $\overline{x_i}$ if $v=x_i$ and $x_i$ if $v=\overline{x_i}$.) \vspace{-3mm} \item[{\it Step 4}.] Select a literal $v$ from $C_{ans}$ such that $N(\overline{v})