
%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})<N(v)$ and replace $v$ in $C_{ans}$ by $\overline{v}$.
Go to Step 3.
\vspace{-3mm}
\item[{\it Step 5}.] Select $t$ literals $w_1, w_2, \cdots , w_t$ 
(with duplication) from the set of $\{ \overline{v_i} | v_i\in
C_{ans}\}$ at random (but not so as to exceed the limit denoted by
$N$) and construct a predicate $f_{now}$ by $f_{now}=(w_1)(w_2)\cdots
(w_t)$.
\vspace{-3mm}
\item[{\it Step 6}.] Select a clause $A$ of less than 3
literals from $f_{now}$ and select a literal $v$ that appears in
$f_{now}$ less than $N(v)$ times. $f_{now}$ is updated by replacing
$A$ by $(A+v)$. Repeat this update until all clauses have 3 literals.
\hspace{\fill}$\Box$
\vspace{-3mm}
\end{description}
\begin{description}
\item[\hspace*{10mm}Generator] 3PRV($0,N$)-GEN:
\vspace{-3mm}
\item[{\it Step 1}.] Select a variable $x_i$ at random and let the 
predicate $f_{now}=x_i\overline{x_i}$.
\vspace{-3mm}
\item[{\it Step 2}.] One of the following (2-1) to (2-3) is 
randomly chosen and executed:
\vspace{-3mm}
\item[\hspace*{3.2mm}({\it 2-1})] Select a clause $A$ in $f_{now}$ 
and select a literal $v$ that appears in $f_{now}$ less than $N(v)$
times, both at random. $f_{now}$ is modified by splitting $A$ into
$(A+v)(A+\overline{v})$. Suppose that a literal $u$ appears more than
$N(u)$ times (i.e., $N(u)+1$ times) in the new $f_{now}$ then select a
clause $B$ of more than 3 literals including $u$ and delete that $u$
from $B$.  If there is no such $B$ then halt with the null output. Do
this for all such $u$.
\vspace{-3mm}
\item[\hspace*{3.2mm}({\it 2-2})] Select a clause $A$ from $f_{now}$ 
including more than 3 literals. Make $A$ include only 3 literals by
deleting literals at random.
\vspace{-3mm}
\item[\hspace*{3.2mm}({\it 2-3})] If all the clauses in $f_{now}$
include 3 literals then go to Step 4.
\vspace{-3mm}
\item[{\it Step 3}.] Repeat Step 2 until the literal distribution is
satisfied and all clauses have 3 literals.
\vspace{-3mm}
\item[{\it Step 4}.] Construct 3-literal clauses at random using the
literals $v$ which now appear in $f_{now}$ less than $N(v)$ times.
Then add those clauses to $f_{now}$.
\hspace{\fill}$\Box$
\vspace{-3mm}
\end{description}

{\bf Theorem 3.} (i)3SAT($N$)-GEN generates all the satisfiable
3-predicates following the literal distribution $N$.
(ii)3PRV($0,N$)-GEN generates all the 3-predicates that follow $N$ and
that are in $L(\mbox{PRV}(0)\mbox{-GEN})$.
\hspace{\fill}$\Box$

(i) is obvious. The following remarks on (ii) would help:
3PRV($0,N$)-GEN may fail (halt with no outputs) depending on the input
$r$. To reduce this probability is a natural research goal. Also note
that at any moment of the algorithm, each literal $v$ appears in
$f_{now}$ at most $N(v)$ times, which contributes to the reduced
failing-probability and makes (ii) above nontrivial.

\section{Future Schedule}

(1)As mentioned in Sec.4. a lot more should be done to manage the
average-case security. We also wish to prove the worst-case security of
those generators satisfying the average-case security by the approach
of Sec.3.

(2)By now much more efforts have been made for generators of
unsatisfiable predicates. Recently, however, we have a strong feeling
that the current version of the satisfiable predicate generators may
need substantial improvements. For example, the current version seems to
involve too much randomness or so-called well-behaved nature.

(3)Implementation of the generators is of course important. At
present, we have implemented the basic algorithms described in Sec.2.
including a very restricted portion of the average-case security.
Testing SAT algorithms by those generators has started very recently
as well.


\begin{thebibliography}{99}
\bibitem{esy84}
S.Even, A.Selman and Y.Yacobi. The complexity of promise problems with
application to public-key cryptography. {\it Information and Control},
Vol.61, 1984.
\bibitem{fra86}
J.Franco. On the probabilistic performance of algorithms for the
satisfiability problem. {\it Inform. Process. Lett.}, Vol.23,
pp.103-106, 1986.
\bibitem{gle89}
O.Goldreich and L.Levin. A hard-core predicate for all one-way
functions. In {\it Proc. 21st ACM Symposium on Theory of Computing},
pp.25-32, 1989.
\bibitem{gse88}
J.Grollmann and A.Selman. Complexity measures for public-key
cryptosystems. {\it SIAM J. Comput.}, Vol.17, No.2, pp.309-335, 1988.
\bibitem{iwa89}
K.Iwama. CNF satisfiability test by counting and polynomial average
time. {\it SIAM J. Comput.}, pp.385-391, 1989.
\bibitem{iam92}
K.Iwama, H.Abeta and E.Miyano. Random generation of satisfiable and
unsatisfiable CNF predicates. In {\it Proc. 12th IFIP World Computer
Congress}, pp.322-328, 1992.
\bibitem{pbr85}
P.Purdom and C.Brown. The pure literal rule and polynomial average
time. {\it SIAM J. Comput.}, pp.943-953, 1985.
\bibitem{san90} 
L.Sanchis. On the complexity of test case generation for NP-hard
problems. {\it Inform. Process. Lett.}, Vol.36, pp.135-140, 1990.
\bibitem{saf90}
L.Sanchis and M.Fulk. On the efficient generation of language
instances. {\it SIAM J. Comput.}, Vol.19, pp.281-296, 1990.
\end{thebibliography}



\end{document}





