24-05-2014, 10:58 AM
PARASITIC COMPUTING
PARASITIC COMPUTING”.doc (Size: 213.5 KB / Downloads: 14)
ABSTRACT
“PARASITE” as the word suggests is an entity that resides on another entity exploiting the resources of the latter. The term “PARASITIC COMPUTING” refers to the technique of using the resources of one computer by another computer without the knowledge of the former. Distributed computing networks turn home users' computers into part of a virtual supercomputer that can perform time-intensive operations. This seminar provides an insight into the details of how parasitic computing uses the computation power of the computers connected to the internet in solving complex mathematical problems. This technique was developed by the scientist at the Notre Dame University, Indiana (USA). According to the scientists, the transmission control protocol (TCP), could be used to solve a piece of a mathematical problem whose answer could then be relayed back to the original user. The implementation is discussed with the NP-Complete problem as example. Unlike hackers who exploit flaws to gain direct access to machines, the Notre Dame computer scientists created a virtual computer by using the fundamental components of distributed computing.
INTRODUCTION
The net is a fertile place where new ideas/products surface quite often. We have already come across many innovative ideas such as Peer-to-Peer file sharing, distributed computing etc. Parasitic computing is a new in this category. Reliable communication on the Internet is guaranteed by a standard set of protocols, used by all computers. The Notre Dame computer scientist showed that these protocols could be exploited to compute with the communication infrastructure, transforming the Internet into a distributed computer in which servers unwittingly perform computation on behalf of a remote node.
In this model, known as “parasitic computing”, one machine forces target computers to solve a piece of a complex computational problem merely by engaging them in standard communication. Consequently, the target computers are unaware that they have performed computation for the benefit of a commanding node. As experimental evidence of the principle of parasitic computing, the scientists harnessed the power of several web servers across the globe, which–unknown to them–work together to solve an NP complete problem.
THE NP-COMPLETE PROBLEM
A problem is assigned to the NP (nondeterministic polynomial time) class if it is verifiable in polynomial time by a Nondeterministic Turing Machine (A nondeterministic Turing Machine is a "parallel" Turing Machine which can take many computational paths simultaneously, with the restriction that the parallel Turing machines cannot communicate.). A problem is NP-hard if an algorithm for solving it can be translated into one for solving any other NP-problem. NP-hard therefore means "at least as hard as any NP-problem", although it might, in fact, be harder. A problem which is both NP and NP-hard is said to be an NP-Complete problem. Examples of NP-Complete problems are the traveling salesman problem and the satisfiability problem.
The `satisfiability' (or SAT) problem involves finding a solution to a Boolean equation that satisfies a number of logical clauses. For example, (x1 XOR x2) AND (x2 AND x3) in principle has 23 potential solutions, but it is satisfied only by the solution x1 = 1, x2 = 0, and x3 = 1. This is called a 2-SAT problem because each clause, shown in parentheses, involves two variables. The more difficult 3-SAT problem is known to be NP complete, which in practice means that there is no known polynomial-time algorithm which solves it. Indeed, the best known algorithm for an n-variable SAT problem scales exponentially with n . Here we follow a brute-force approach by instructing target computers to evaluate, in a distributed fashion, each of the 2n potential solutions.
THEORY
To solve many NP complete problems, such as the traveling salesman or the satisfiability problem, a common technique is to generate a large number of candidate solutions and then test the candidates for their adequacy. Because the candidate solutions can be tested in parallel, an effective computer architecture for these problems is one that supports simultaneous evaluation of many tests.
Four Notre Dame professors recently discovered a new Internet vulnerability that is commonly known as "parasitic computing." The researchers found a way to "trick" Web servers around the world into solving logic math problems without the server's permission. The researchers found that they could tag a logic problem onto the check sum (the bit amount that is sent when a Web page is requested) and the Web server would process the request. When a Web page was requested without the correct check sum, the server would not respond to the request.
Each of the math problems that were tagged on to the request by the researchers was broken down into smaller pieces that were evaluated by servers in North America, Europe and Asia. The results from each were used to build a solution. Using a remote server, the team divided the problem into packages, each associated with a potential answer. The bits were then hidden inside components of the standard transmission control protocol of the Internet, and sent on their merry way.
Computing with TCP
The implementation of parasitic computing exploits a reliability mechanism in the transmission control protocol (TCP). During package transfer across the Internet, messages can be corrupted, that is, the bits can change. TCP contains a checksum that provides some data integrity of the message. To achieve this, the sender computes a checksum and transmits that with the message. The receiver also computes a checksum, and if it does not agree with the sender's, then the message was corrupted The sender of a TCP segment computes a checksum over the entire segment, which provides reliability against bit errors that might occur in transport.