" If this occurs, the packet is retained as good and is passed to the application layer for action; ifnot, the packet is dropped and TCP waits for a pre-arranged retransmission of thepacket by thesending computer. The TCP checksum function performed by the receiving computer is, in essence, afundamental “add-and-compare” procedure, which forms the basis for any other Boolean orarithmetic operation. As a consequence, TCP can be exploited to perform computations without”invading” (i.e., hacking or cracking into) those systems induced to participate. In this sense,then, parasitic computing is a “non-invasive” form of covert exploitation that does not penetratebeyond the TCP/IP layers the host. This differentiates parasitic computing from the othermethods described above for capitalizing on IP-related vulnerabilities. 10 PROBLEMS SOLVED USING PARASITIC COMPUTINGNP-COMPLETE SATISFIABILITY PROBLEMThe problem that we are addressing is called the “satisfiablity” problem, which means, decidingwhether a given Boolean formula in conjunctive normal form has an assignment that makes theformula "true." In 1971, Cook showed that the problem is NPcomplete. Before we define whatthe problem is, we must know what a conjunctive normal form means and what is NP- completeness.CONJUCTIVE NORMAL FORMA statement is in conjunctive normal form if it is a conjunction (sequence of ANDs) consistingof one or more conjuncts, each of which is a disjunction (OR) of one or more literals. Everystatement in logic consisting of a combination of multiple , , and scan be written in conjunctivenormal form. A disjunctive normal form (DNF) is a similar expression, which joins the clausestogether with ORs.Satisfiability arises whenever we seek a configuration or object that must be consistent with(i.e. satisfy) a given set of constraints. The input to the problem could be a set of clauses inconjunctive normal form. The problem is to determine whether there is a truth assignment to theBoolean variables such that every clauses is simultaneously satisified.Satisfiability is the originalNP-complete problem.EXAMPLE OF SATISFIABILITY PROBLEM2-SAT PROBLEMTo implement a parasitic computer using the checksum function we need to design a specialmessage that coerces a target server into performing the desired computation. As a test problem 11 we choose to solve the well known `satisÆability' (or SAT) problem, which is a common test formany unusual computation methods4,5. The SAT problem involves Ænding a solution to aBoolean equation that satisÆes a number of logical clauses. For example, (x1 XOR x2)AND(,x2 AND x3) in principle has 23 potential solutions, but it is satisÆed only by the solutionx1 à 1, x2 à 0, and x3 à 1. This is called a 2-SAT problem because each clause, shown inparentheses,involves two variables.To demonstrate how this exploitation of the TCP checksum function was possible, Barabasi etal. (2001) elected to solve an NP-complete satisfiability (SAT) problem via distributedcomputing. As described by these authors, the specific version of the problem was a 2-SATvariant involving a Boolean equation with 16 binary variables related by AND or XOR operators(see Barabasi, et al., 2001, Fig. 3, for more details). The method used to solve this probleminvolved parallel evaluations of each of the 216 possible solutions. To accomplish these parallelevaluations, a TCP/IP Checksum Computer (TICC) was devised (see Freeh,2002) that couldconstruct messages containing candidate solutions to the problem, which were then sent, alongwith a template for determining the correct solution, over the Internet to a number of target webservers in North America, Europe, and Asia. Similar to the behavior of a biological “parasite,”the TICC acted to take advantage of the targeted “hosts” by inducing them to evaluate thecandidate solutions they received against the correct solution template and return for each one abinary, “yes/no” decision to the TICC.Inducement without security compromise (i.e., invasion) was achieved by exploiting the TCPchecksum function on each targeted host. The parasitic TICC constructed special messagepackets for each host and injected them directly into the network at the IP layer. These messagescontained one of the possible 216 candidate solutions encoded as packet data in two sequential16-bit words, along with a 16-bit version of the correct solution (in complemented form)substituted in place of the normal TCP checksum value. When the packet was received by thehost computer, the two 16-bit words containing the candidate solution, which werepresumed by the host to be packet data, were added together with the complemented checksum(i.e., the correct solution) according to the usual operation of the TCP checksum functiondescribed above (see Barabasi, et al., 2001, Fig. 3, for more details). If the enclosed candidatesolution was a correct one, then its one?s complement binary sum would combine with the 12 "