ࡱ > , . ' ( ) * + M p bjbj== ~ W W _ B m l " Za Za Za 8 a b T U c i : 6j 6j 6j ߲ _ c T T T T T T T $ OW oY f T g y f ߲ g g T 6j 6j CA UU g 6j 6j T g T J ~ 2L S 6j c N Za ^ O X S kU 0 U
P Y { < Y S
Fraud Tolerant Distributed Computing
By
Shruti Parihar
Advisor: Dr. Mark Stamp
Committee: Dr. Chris Pollett
Dr. David Blockus
Department of Computer Science, One Washington Square San Jos, California USA 95192Table of Contents
TOC \o "1-4" \h \z HYPERLINK \l "_Toc56509207" Chapter 1 PAGEREF _Toc56509207 \h 6
HYPERLINK \l "_Toc56509208" Introduction PAGEREF _Toc56509208 \h 6
HYPERLINK \l "_Toc56509209" 1.1 Motivation PAGEREF _Toc56509209 \h 6
HYPERLINK \l "_Toc56509210" 1.2 Background and History PAGEREF _Toc56509210 \h 6
HYPERLINK \l "_Toc56509211" 1.3 Applications of Distributed Computing PAGEREF _Toc56509211 \h 8
HYPERLINK \l "_Toc56509212" 1.4 Issues in Distributed Computing PAGEREF _Toc56509212 \h 10
HYPERLINK \l "_Toc56509213" 1.5 Fraud issues in Volunteer Computing PAGEREF _Toc56509213 \h 14
HYPERLINK \l "_Toc56509214" 1.6 Research Objective PAGEREF _Toc56509214 \h 16
HYPERLINK \l "_Toc56509215" Chapter 2 PAGEREF _Toc56509215 \h 17
HYPERLINK \l "_Toc56509216" System Design and Model PAGEREF _Toc56509216 \h 17
HYPERLINK \l "_Toc56509217" 2.1 Peer-to-Peer Models PAGEREF _Toc56509217 \h 17
HYPERLINK \l "_Toc56509218" 2.2 Distributed Computing Model PAGEREF _Toc56509218 \h 18
HYPERLINK \l "_Toc56509219" 2.3 Software Design PAGEREF _Toc56509219 \h 20
HYPERLINK \l "_Toc56509223" 2.4 System Design PAGEREF _Toc56509223 \h 28
HYPERLINK \l "_Toc56509224" Chapter 3 PAGEREF _Toc56509224 \h 34
HYPERLINK \l "_Toc56509225" System Architecture PAGEREF _Toc56509225 \h 34
HYPERLINK \l "_Toc56509226" 3.1 System Architecture PAGEREF _Toc56509226 \h 34
HYPERLINK \l "_Toc56509227" 3.2 Resource Management PAGEREF _Toc56509227 \h 35
HYPERLINK \l "_Toc56509228" 3.3 Job Scheduling and Load Balancing PAGEREF _Toc56509228 \h 39
HYPERLINK \l "_Toc56509229" 3.4 Peer Resource Usage PAGEREF _Toc56509229 \h 41
HYPERLINK \l "_Toc56509230" Chapter 4 PAGEREF _Toc56509230 \h 46
HYPERLINK \l "_Toc56509231" Fraud Resilience PAGEREF _Toc56509231 \h 46
HYPERLINK \l "_Toc56509232" 4.1 Motivation PAGEREF _Toc56509232 \h 46
HYPERLINK \l "_Toc56509233" 4.2 Cheat Resistant Scheme PAGEREF _Toc56509233 \h 46
HYPERLINK \l "_Toc56509234" 4.3 Authentication Protocol PAGEREF _Toc56509234 \h 58
HYPERLINK \l "_Toc56509235" Chapter 5 PAGEREF _Toc56509235 \h 60
HYPERLINK \l "_Toc56509236" Results PAGEREF _Toc56509236 \h 60
HYPERLINK \l "_Toc56509237" 5.1 Test Environment PAGEREF _Toc56509237 \h 60
HYPERLINK \l "_Toc56509238" 5.2 Ringers PAGEREF _Toc56509238 \h 60
HYPERLINK \l "_Toc56509239" 5.3 Server Performance PAGEREF _Toc56509239 \h 61
HYPERLINK \l "_Toc56509240" 5.4 Analysis of Results PAGEREF _Toc56509240 \h 62
HYPERLINK \l "_Toc56509241" Chapter 6 PAGEREF _Toc56509241 \h 63
HYPERLINK \l "_Toc56509242" Conclusion and Future Work PAGEREF _Toc56509242 \h 63
HYPERLINK \l "_Toc56509243" 6.1 Concluding remarks PAGEREF _Toc56509243 \h 63
HYPERLINK \l "_Toc56509244" 6.2 Future Work PAGEREF _Toc56509244 \h 64
HYPERLINK \l "_Toc56509245" Appendix A: Annotated Bibliography PAGEREF _Toc56509245 \h 66
HYPERLINK \l "_Toc56509246" Appendix B: Glossary PAGEREF _Toc56509246 \h 70
List of Figures
Figure 1. Peer Design MVC Architecture 22
Figure 2. XML File to Record Batch Job 24
Figure 3. XML File to Record Results 27
Figure 4. Server System Design 29
Figure 5. Peer System Design 32
Figure 6. System Architecture 34
Figure 7. XML Structure for Job Requirements 38
Figure 8. Peer Break-off Algorithm 43
Figure 9. Variable Re-composition for Strings 55
Figure 10. Variable Re-composition for Integers 55
Figure 11. A Simple Java Class Before obfuscation 56
Figure 12. Obfuscated Java Class 57
List of Tables
Table 1. Ringer Number Tests 61
Table 2. Server Scheduling Tests 62
Chapter 1
Introduction
1.1 Motivation
Scientists have always explored ways to increase computing power to satisfy growing computation needs. Recently, attempts have been made to use inexpensive, powerful workstations to form workstation clusters for parallel and distributed processing. A workstation cluster can offer high performance and throughput by distributing the load onto many workstations. They can off-load jobs from vector supercomputers, often providing comparable through put at a fraction of the cost. If workstations within clusters have a high speed interconnect, they may also serve as an inexpensive parallel computer. However, a collection of inter-connected workstations crossing geographical boundaries does not constitute a distributed computing system. A distributed resource management system must be employed so that the total aggregate power of the cluster can be efficiently distributed across a wide user base.
1.2 Background and History
The concept of distributing load to several workstations has been around for a long time. Early justifications of ARPANET( describe the use of networked computational resources. Subsequent inventions like Ethernet provided for high bandwidth networking and distributed processing. In the early 1990s several academic projects like Condor were initiated, to use several Unix workstations in distributed computing projects [9]. The idea was to gain high throughput over a long period of time by distributing workload to many machines. These early distributed computing systems focused on developing efficient algorithms for scheduling resources, load balancing and efficient job scheduling amongst a pool of participants. However, these systems provided no special support for security and unobtrusiveness, particularly in the case of invasive applications. Furthermore, they did not adapt to the heterogeneity of computing resources well. They were platform specific, limited in what was allowed in application execution and incurred a significant management effort for each machine.
With the proliferation of internet-users and high-speed connectivity to the Internet, several projects came up that tapped CPU resources of Internet users. Also known as volunteer computing, these projects targeted the enormous CPU power in work places, homes and institutions, which was largely unused. One such project to search for extraterrestrial life, known as SETI@HOME, started in Berkeley in 1997 [23]. The distributed application is downloaded in the form of a screen saver, which scans radio signals received from large telescopes in Puerto Rico, for specific patterns alluding to life in outer space.
Project Bayanihan is another step in the direction of volunteer computing or meta-computing, which enables people to form large parallel computing networks using ubiquitous technologies like Java-based browsers [16]. It provides a framework for users to write distributed applications in the form of applets. Participants can contribute their CPU processing power by accessing a URL via their browsers. The applet executes using client resources, processing jobs assigned by the server.
The Charlotte system separates the execution environment from the inherent parallelism in the programmers algorithm and programming language [5]. The system enables programmers to write parallel programs in Java and Java-based browsers. A virtual machine abstraction is provided which separates the execution environment from the parallel program logic. The rationale used is that the execution environment being the World Wide Web, is inherently unreliable, distributed and heterogeneous in resources. Availability of machines changes over time and network connections vary significantly. The virtual machine provides a runtime system that executes user-specified parallel programs on this platform. Crucial management tasks for the distributed environment like load balancing and job scheduling are performed by the virtual machine. It also bypasses participating machines that are slow, hav e c r a s h e d o r h a v e b e e n t a k e n a w a y , h e n c e m a i n t a i n i n g t h e c o h e r e n c e o f d i s t r i b u t e d d a t a .
A p p l i c a t i o n s o f D i s t r i b u t e d C o m p u t i n g
T h e m o s t a p p r o p r i a t e a p p l i c a t i o n s , a c c o r d i n g t o E n t r o p i a "! [ 2 ] , c o n s i s t o f " l o o s e l y c o u p l e d , n o n - s e q u e n t i a l t a s k s i n b a t c h p r o c e s s es with a high compute-to-data ratio." In other words, it should be possible to partition the application into independent parallel tasks, adhering to coarse-grained parallelism. Most suitable applications are those, which do not require communication and data sharing between concurrent tasks. Another important consideration is the ease of division of data into separate domains that can be assigned to concurrent tasks. Each of these tasks and data chunks should be such that they can be effectively processed on modern PCs within a timeframe ranging from a few hours to a few days. A possible classification of applications is as follows:
Query search applications involving large volumes of data that cannot be searched by one query process. The data can be divided into chunks that are independently and concurrently searched by the submitted query on several desktops.
Complex modeling and simulation techniques often require several trials on each subtask for accuracy and statistical significance. Distributing applications like these can enable parallel processing of random trials on different desktops. Financial risk analysis is an example of such applications.
Exhaustive search techniques that require searching through a huge number of results to find solutions to a problem are also potential applications. Key search problems involving exhaustive searches of cipher keys like DES, RSA etc are examples.
Many of today's vendors, part i c u l a r l y E n t r o p i a "! a n d U n i t e d D e v i c e s "!, [ 1 5 ] a r e t a r g e t i n g t h e l i f e s c i e n c e s m a r k e t . T h e s c i e n c e o f g e n e t i c s a n d g e n o m e s e q u e n c i n g h a s p o t e n t i a l a p p l i c a t i o n s f o r d i s t r i b u t e d c o m p u t i n g . A n e x a m p l e i s t h e p r o c e s s o f m a t c h i n g c o m p l e x m o l e c u l e s a n d c o m p o u n d s t o newly found proteins for pharmaceutical firms in drug manufacture. The process of matching all these patterns to their appropriate targets is an ideal task for distributed computing. Another related application is the recent trend of generating new types of drugs on computers.
Complex financial modeling, weather forecasting and elaborate car crash simulations are applications of commercial systems based on distributed computing.
1.4 Issues in Distributed Computing
1.4.1 Scalability
Scalability is an important deciding factor in the design of a distributed computing system. Parallel systems like PVM and Calypso [6] are adaptive systems and have built-in resource managers which can dynamically add explicitly named machines to the system. On Unix-based distributed systems, the rsh command and the rexec() system call are the common underlying mechanisms to start program executions on remote machines. This system design can be applied to a LAN setting where all participants are networked. User access privileges have to be taken into account in remote login mechanisms such as these. One would need administrator privileges on all networked workstations to administer the distributed system and start processes on remote machines.
For distributed systems that target global CPU resources via the Internet, this system design is not appropriate. Different scalable designs that have been used are Java stand- alone applications, applets and screen savers. Java provides a platform independent way to develop distributed applications. The Java virtual machine abstracts low-level platform specific details, making the Java platform a good choice for a heterogeneous environment like the Internet. Participants typically download and install the application on their computers and can control their CPU resource contribution.
1.4.2 Security
With a distributed system targeted for users all over the world, security and protection of privacy are important considerations. A framework for distributed applications must protect the integrity of the computation. The framework should be robust and fraud resilient to attacks by malicious users as they can tamper with application data and programs. The distributed computing system must also protect the integrity of the computing resources that it is aggregating. Users must be protected too, against applications as they may access personal data and files on their c o m p u t e r s . T h e E n t r o p i a "! s y s t e m a d d r e s s e s t h i s s e c u r i t y i s s u e b y u s i n g s a n d - b o x i n g t e c h n i q u e s , [ 2 ] . T h e a d v a n t a g e s o f a s a n d b o x a r e t w o f o l d . A s a n d b o x p r o v i d e s p r o t e c t i o n t o t h e u s e r s d a t a a n d f i l e s f r o m m i s b e h a v i n g a p p l i c a t i o n s . I t a l s o p r o t e c t s t h e a p plication and data from being tampered with by users. The sandbox isolates the distributed application and makes sure it cannot invoke inappropriate system calls or modify the desktop disk, registry or machine configuration. It also restricts the Windows APIs available to the application, protecting system resources from being abused. The sandbox protects application data and results by encrypting them and preventing access to them by other applications. It performs periodic integrity checks and reschedules sub-jobs if their data or results have been tampered with.
1.4.3 Resource Scheduling
The performance of any distributed or grid application largely depends on the resource management algorithm used. A work cluster can comprise machines with different operating systems, hardware configurations such as memory, disk space and I/O speed, and processors. Typically distributed systems are designed for different applications, which may differ in their requirement of resources. The system must adapt to these requirements efficiently.
The Condor system uses a dynamic resource-scheduling algorithm, which tries to delegate jobs to appropriate machines, based on availability of resources and requirements submitted by users [9]. Condors resource management techniques of Matchmaking and Classads, allow for dynamic advertisements of resource availability and requirement. In other words, both givers and receivers can dynamically specify the nature of requirement or resource available in order to find a suitable match. Matchmaking is the process by which Resource Offers and Resource Requests that satisfy each other are identified and paired up together. The Classified Advertisement Language (Classad) specifies the characteristics, constraints and preferences of users and participants. The Classad language is a symmetric description language, which is used by both service providers and requesters. By using the same language to describe characteristics, constraints and preferences of requirements and available resources, finding suitable matches is easier. Among other constructs, that allow entities to be easily represented, the language supports semi-structured records that are used for entity descriptions. For more information, refer [7].
1.4.4 Job Scheduling and Testing
The key to writing distributed applications is to write parallel programs and distribute jobs to individual participants. Job scheduling refers to the break up of large jobs to smaller manageable chunks, which can be parallel processed by several participants. Depending on the nature of the application, this division can be primarily of data or functionality. This research study is focused on distributing cipher key searches among a dynamic group of participants. Job scheduling is therefore limited to a breakup of data for individual sub-jobs. A similar approach is used in the SETI@HOME project, where the application is distributed in the form of a screen saver and the server breaks down sampled signals to fixed bandwidth portions.
A related aspect is data dependencies amongst multiple job packets and inter-peer communication amongst participants with different sub-jobs. The results processed by one participant may be needed by another, which will require a way to index and search results, preferably on the server, so that peers can query for required results. The application should also test for the integrity and correctness of results. Some systems use random spot checks on participants and blacklist untrustworthy ones for future job delegation. Another approach is to overlap some part of the data domain amongst multiple participants, and verify that results are identical in all cases.
1.4.5 Fault Tolerance
In distributed systems there is ample potential for faults and failures such as network connectivity problems, hardware malfunctioning, system reboots resulting in loss of data etc. Some systems have addressed this issue with solutions providing fail-over, redundancy of servers, etc. Condor provides a Checkpointing mechanism to write out checkpoints during job processing. These checkpoints are in the form of files written to disk by the application containing information about the program data and stack segments, open files, CPU state etc. This information is used to resume processing of jobs later.
1.5 Fraud issues in Volunteer Computing
Much of the research in the field of fault tolerance in distributed environments has addressed issues pertaining to software and hardware failures. Little work has been done to address the problem of erroneous computations, much less of intentional fraud. Volunteer computing includes participation of users all over the world. Being a relatively new variation to distributed computing, internal sabotage by users, is a problem faced only in recent times. The SETI@HOME project has faced fraud issues, where participants try to reverse engineer the application in order to produce incorrect results of work done and claim credit of work they did not do. Sometimes users tweak the application to perform better but inadvertently disrupt accuracy of application performance. The problem gets magnified in the case of commercial systems, where users get paid for their contributions. The case of false positives may be feasible to detect in some applications, where the server can re-compute those results without much overhead, and verify correctness of computations. However, the case of false negatives, or claiming results are not found, can be infeasible to detect in cases where results are rare. Examples of such applications are key searches, where only one key satisfies the search criteria. If a user incorrectly claims that the key is not found without attempting to search his key space, the server cannot re-compute the key space for all such cases.
Some distributed systems have addressed fraud issues with sand-boxing techniques (for example, E n t r o p i a "!, a s d i s c u s s e d a b o v e ) , r a n d o m s p o t c h e c k s o f r e s u l t s s e n t , d i g i t a l s i g n a t u r e s f o r p e e r a u t h e n t i c a t i o n , c o d e o b f u s c a t i o n , c h e c k s u m s e t c . I n o r d e r t o c o m p e l u s e r s t o c o m p l e t e t h e j o b t o g e t c r e d i t f o r w o r k , c h e c k s u m s a r e a d d e d t o t h e r e s u l t s t h a t a re checked by the server each time results are sent. This scheme may not work if a user manages to reverse byte-codes and produce the source code of the application and determine how the checksum is computed. A user may then fabricate false results with the right checksum. Techniques to combat attacks such as these include code obfuscation to confuse the user of the application and checksum logic. Changing the checksum algorithm periodically may discourage saboteurs too. Redundancy in job scheduling is also a technique used in some systems to detect cheaters. The same job is given to multiple participants and their results are compared. Assuming that there are more good users than bad, consistent results will eventually be found.
1.6 Research Objective
During the course of this research study, I have analyzed various distributing computing environments and studied mechanisms for fraud protection. I have particularly researched applications to perform distributed searches for cipher keys like the TEA cipher. Applications like these are computationally intensive and can be broken down into mutually independent tasks. I have used a fraud protection model proposed in [20] and have customized it to my application. The scheme detects job evasion by saboteurs in volunteer computing settings by setting milestones of job completion and later scanning results sent for their presence, in order to ascertain what percentage of the job was done. The strength of the fraud protection model lies in concealing information about the milestones, so that malicious users cannot detect them and hence are compelled to complete their work in order to get credit for it. I have proposed a variant to the original model and have implemented it. Later chapters have empirical results demonstrating the effectiveness of the model in protecting against a large number of attacks in a distributed computing scenario.
Chapter 2
System Design and Model
2.1 Peer-to-Peer Models
Peer-to-peer networks aim at harnessing the capacity and capabilities of numerous personal computers all over the world. They aim at creating a cluster of workstations that work in tandem toward a common goal, which could be sharing data, performing computations etc.
The following models are some of the variations of peer-to-peer systems, according to [10, 3]:
A pure p2p network model comprises peers, which talk amongst themselves, share content and resources. They essentially request service to other peers as well as respond to the requests of others. Peers make direct contact with each other, using complex search algorithms for online peers.
A variant to the above model includes a server, which maintains a database of peer information. Online peers contact the server, indicating that they are online. The server gives initiators information about other peers. However, server responsibility is limited to giving information, once located, peers communicate directly amongst themselves.
Another p2p model is one in which the server could be given added functionality such as indexing data and resources shared by online peers, so that a peer requiring some resource can contact the server for information about which peer may have it. The server will hence, also maintain content/resource information of peers.
This p2p model does away with inter peer communication, but still assumes that resources are distributed and shared in the network. Peers requesting resources contact the server, which searches and returns results to them. In other words, the server maintains peer and content information and fetches the resource for the requesting peer. Peers need not communicate with each other for exchange of data.
All of the above models have certain aspects common to the system. These are:
Tracing fellow peers: peers need to communicate with other peers for some shared resources. This can occur thru a server or directly, depending on the system design.
Querying peers for content
Sharing resources with other peers
2.2 Distributed Computing Model
2.2.1 Introduction
According to a recent article on Distributed Computing in ExtremeTech [15], One can define distributed computing in many different ways. Various vendors have created and marketed distributed computing systems for years, and have developed numerous initiatives and architectures to permit distributed processing of data and objects across a network of connected systems.
In recent years, distributed computing systems have been used to harness idle CPU cycles and storage capacity of computers all over the world. Also referred to High Throughput Computing (HTC), this technology aims at building clusters of workstations, which can work in tandem toward a common goal. The intent is to have tremendous gain in throughput over a period of time. Cluster computing is characterized by management nodes, which perform tasks like registering participants, job scheduling, job pool management, resource sharing, security, authentication, etc. Typically, resources like data, computing power, physical memory, etc. are distributed and heterogeneous and are shared amongst cluster members. The optimum division of labor in cluster environments is a problem open to much research and experimentation. Cluster computing is a drift from the conventional, centralized client-server model, in that cluster participants distribute workload amongst themselves, leaving specialized management tasks to servers. The peer-to-peer model is at the other extreme, with a decentralized architecture, wherein peers can act as request servers and makers. Typical distributed computing systems, deploy management techniques, which are a balance between the above two methodologies. Several factors like network- bandwidth and service point bottlenecks control network management decisions.
The field of distributed computing has been subject to much academic research, particularly in areas of security, management and network communication. The last few years have seen a new interest in the idea after the technology spun off from the peer-to-peer trend started by Napster [15]. A number of new vendors have appeared to take advantage of the nascent market; including major technology companies such as like Intel, Microsoft, Sun, and Compaq that have validated the importance of the concept [15]. Increasing desktop CPU power and communications bandwidth, have also helped to make distributed computing a more practical idea.
Software Design
In developing a distributed system for key searches, I have used a server-peer model. The server is central to system management and manages peers while they dynamically join the system. Peers on the other hand perform parallel, distributed tasks delegated to them by the server. Peers perform resource management of the system available to them and process tasks given to them. The server handles load balancing and testing of results sent back.
2.3.1 Object-Oriented Design
The object-oriented design paradigm focuses on software, reusability using inheritance, polymorphism and encapsulation [19]. Software reusability helps enhance software development productivity and quality. In implementing the system, I have focused on these object-oriented design principles. I have developed APIs for communication between server and peers, job scheduling, result analysis, job pool management and job processing on the peer side.
2.3.2 MVC Architecture
The Model View Controller (MVC) paradigm proposes explicit separation of the user input, the modeling of the external world, and the visual feedback, all of which are handled by three types of objects, each specialized for its task [19]. The view manages the graphical and/or textual output to the display objects allocated to its application. The controller, as its name suggests controls the flow of the application process by interpreting the mouse and keyboard inputs from the user and appropriately commanding the model and/or the view to change. Finally, the model encapsulates the business logic and functionality of the application. It responds to requests for information about its state and to instructions to process some business function (usually from the controller).
I have adopted the Model-View-Controller design paradigm in keeping with scalability and ease of reuse. The major system components are the server and peer. The design of each of these adheres to the MVC paradigm. The peer application is divided into the following major components:
The GUI helps users interact with the application. A participant can install the software, register himself and view work in progress using various view objects.
The central thread of control comprises system agents to monitor keyboard, mouse activity etc, and handles to other logic modules. It represents the controller object.
The worker thread is spawned when system is idle and represents the model object. The worker in turn invokes various modules for server communication, job processing, result writing etc.
A separation of major logic components is a scalable software design. For instance, should we require that peer authentication be done, we can add a module for digital certificate processing in the communication module. Similarly, views can be added or modified without much change to the overall software system. The following figure illustrates the overall peer software design.
SHAPE \* MERGEFORMAT
Figure 1. Peer Design MVC Architecture
The server system is modeled using a similar design. The user interface is limited to simple consoles and log files which trace out server activity. Internally, all major logic components are separated out and connected through a central server thread.
2.3.3 Technology Platform
The system is implemented in Java and XML. Java technologies, being platform independent, are a natural choice for a distributed system, which may be deployed at different environments. XML is a convenient, platform-independent standard for data structuring and messaging. By deploying XML for data storage and retrieval, the system can be integrated easily with third-party software and is flexible and scalable.
2.3.4 XML Standard
2.3.4.1 Introduction
XML is a standard for structuring data and separating presentation specifics from content [26]. In recent years, the XML data format has been used widely in a variety of information system solutions. Applications where XML is used include document transmissions in B2B systems, messaging between different internet-based applications, data storage, retrieval and manipulation. XML is the format of choice due to its platform independence, portability and ability to share data. Moreover, it can accommodate text, images and sound files as attachments. Amongst disadvantages of using XML are its overhead in data conversions, new skill requirements and management issues of XML data.
Databases are ubiquitous with business and Internet based software applications. With the growing popularity of XML for data storage, database compatibility of the XML standard is a must. Most databases are relational, which means that XML documents should efficiently process relational data. The hierarchical format of the XML standard makes it possible for data conversions in different ways between XML documents and relational databases. However, now new XML database products are built to handle XML data demands natively without the overhead of converting to other database structures such as the relational structure. In addition, a variety of XML storage strategies, conversion processes, and levels of support for XML with the leading database products have been developed with the growing popularity of XML.
XML documents are primarily of two types
Data-centric
Document-centric
Data-centric documents have well-defined structures and are used mostly as invoice, purchase orders, newspaper content etc. The size and structure are quite predictable.
Document-centric data tends to be unpredictable in size and structure as they have flexible rules for optional fields and content.
2.3.4.2 Role of XML
In this project, I have used XML as a standard to store data about peers on the server, to record job information delegated to peers by servers and write results of computations by peers. I have used structured data-centric documents, which are updated frequently on the server as well as by the peer software. The advantages of using XML are as follows:
Portability XML being a platform-independent standard makes software systems portable as data encoding and decoding issues can be avoided by using a single text-based standard.
Easy Messaging Standard XML is an evolving standard for messaging between applications across networks. It also provides for capabilities to attach binary files to messages etc.
Well Structured XML provides a well-defined structure to files and messages that can be imposed by an XML schema. This allows for easy integration with other systems and validation of data integrity and correctness.
Ease of Data storage and retrieval This is facilitated by extensive APIs in Java. Integrating XML data with relational databases is possible too.
Flexibility The XML standard and XML schema provide a flexible way to structure data and separate data content from presentation. Related technologies like XSLT and XPATH allow developers to present XML data in various forms in editors and tools.
The server maintains a record of every session with a peer. All peers have unique peer names, which identify them. Information stored is what jobs were given as part of the batch job (in this system a job would indicate the specific space to search for the key), what the ringers( were in those jobs and what ringer images( they mapped to. Job status is recorded for each job given and updated after results are returned. This gives the flexibility to have multiple values for the status field, so that the job can be re-assigned.
The peer application writes out details of the batch job, once received, in an XML file. It records information like the key space to search in each job packet, status of job completion and session information. When initialized, the worker module reads the next unfinished job information from this file. A separate file is maintained for results. This file is updated as and when job packets are processed. When there are no more unfinished jobs left, the peer connects to the server and sends its results. The server in turn gives the peer another batch job to process. The following are examples of XML file structures used.
0
31
0
127
0
255
0
255
--
--
Figure 2. XML file to record batch job
The above snippet is taken from myJobs.xml, which is produced when the peer receives a batch job from the server. A single batch may have many job packets, which are recorded as shown. In this example, job packet named packet1 is a job to scan the space 0-31, 0-127, 0-255, 0-255, which indicates that the key space to search is represented by the limits 0-31 of the first byte, 0-127 of the second, 0-255 of the third and 0-255 of the fourth. Hence, a 32-bit key is being searched. A status of false indicates that the job has not been completed.
Similarly, figure 3 illustrates the myResults.xml file, which records results of completed jobs.
0
31
0
127
0
255
0
255
13 103 23 100
1 29 52 24
Figure 3. XML file to record results
The file indicates that the job named packet1 is complete. Two ringers were found with values 13 103 23 100 and 1 29 52 24. In this job, no keys were found. If a key had matched the search criteria, (in this case encrypted plain text to cipher text), it would have been recorded as a child of the potentialkey node.
2.4 System Design
The following are key elements in the overall system design.
A server component, which is a single dedicated machine. A network (LAN) server is implemented for smaller computing environments, although a scalable web based server would be appropriate for larger projects. The server has a layered architecture: Communication Layer, Data Layer and Job Layer. The communication layer comprises the messaging module and the network communication module. The Job Layer has the Central Manager, Job scheduler and Screener factory modules. The Data Layer consists of the XML processing module.
XML data storage for online peer information, job information and results.
A peer component, which is installed on user machines. The peer component can be further divided into three major modules: Communication Layer, Performance Layer and User Interface Layer.
2.4.1 Server Design
SHAPE \* MERGEFORMAT
Figure 4. Server System Design
Communication Layer
The communication layer implements network communication using TCP/IP protocols. The functionality is implemented in the class GlobalSocket, which is inherited by GlobalSocketServer and GlobalSocketPeer classes.
Data Layer
The data layer implements XML processing of data storage, retrieval and manipulation. The XMLFactory, PropertyLocator and AppConfiguration classes constitute the data layer. The PropertyLocator class manages properties files used to configure the system. The AppConfiguration object represents important system information configured at that time, managed via init() and update() methods. Information stored about peers includes peer names, ringers, ringer hashes, batch jobs sent, etc.
Job Layer
The job layer contains most of the system logic for job scheduling, load balancing, testing, ringer management etc, in various inter-dependent objects.
The Scheduler class performs the task of job assignment to peers, choosing from a pool of pending tasks, managed by the PendingJobPoolMgr class. It uses an algorithm for assignment of jobs of a certain size, which is configurable, in method nextJob(). The peer will receive a job that will last for some days/hours. An optimum job size will factor network bandwidth and traffic. Shorter job assignments, will lead to more traffic periodically, as the cluster grows, since peers will be connecting to the server more often.
The ScreenerMgr object is used to get a different random version of the screener ( application, via the getScreenerHandle() method. Different versions of the screener application are maintained and one is randomly chosen for a peer.
Verification and testing of results sent by peers is done in the VerificationFactory class. This object will basically query server data files for ringers that were assigned for the job and verify that the peer returned all of them. It will also re-compute any keys returned by peers as found results.
Authentication Layer
The fraud resistant model proposed includes peer authentication via digital certificates. However, this module is not implemented. An authentication layer can be added and integrated with the communication layer.
2.4.2 Peer Architecture
SHAPE \* MERGEFORMAT
Figure 5. Peer System Design
User Interface Layer
The User Interface Layer includes objects to view results, register with the server and system agents, which monitor keyboard and mouse activity. A plausible technique to detect user activity on a computer is to monitor keyboard and mouse activity. If there is no activity for a certain period of time (a value the user can specify), one can assume that the user is probably not using his computer. The system activity agents developed in this project follow this approach.
The ResultViewer class provides a simple tool to view results and job progress. The results and job batch files are in XML format. Using XSLT modules to convert XML data to HTML, this tool enables the user to view a summary of job progress, server error messages, results computed etc.
Performance Layer
The DiscompPeer object stays alive once the peer software is installed. It glues the various components of the system together. System agents are programs written using native code and the DiscompPeer has handles to them. A Worker thread is spawned for job processing. The Screener class has a match_ringer() method, which accepts a hash value and ascertains if it is a ringer hash. It records found ringers and potential keys in result files.
Communication Layer
This layer allows XML messages to be sent and received.
Chapter 3
System Architecture
3.1 System Architecture
SHAPE \* MERGEFORMAT
Figure 6. System Architecture
3.2 Resource Management
The resource manager uses a dynamic resource allocation strategy to adapt to heterogeneous network environments. Peers may join and leave dynamically, which makes it impossible to ascertain the availability of resources at any time, statically. Hence, the resource manager determines optimal job assignments to participant workstations depending on requirement definitions and system specifics and configuration of workstations. Applications like key search, prime number generation, protein folding, etc. are viable for a distributed computing system such as this. They too may differ in their requirements for resources, such as RAM, CPU speed, external storage drives, operating system, hard disk capacity, maximum number of dedicated workstations, etc. The resource manager maintains all requirement definitions in the Requirements Pool. Users wishing to submit a job with specific requirements may do so, in a format discussed later. All requirement definitions are stored in XML files on the server and periodically updated to the requirements pool in memory. This is done primarily for efficiency reasons and an optimum refresh strategy can be computed.
When a peer connects with the server for a batch job to process, it sends specific system information in an XML message. The resource manager has a matching algorithm, which will ascertain the most suitable application for that peer, by examining the requirements pool and the system information sent by the peer. The strategy used is discussed in more detail in the next section. Once assigned, the resource manager will update the requirements pool, to reflect a batch job assignment to the peer and compute a unique id for that application. This information will later be stored in the jobs given to the peer, so that appropriate handling at later stages (testing and verification, pending pool assignment, etc.) can be done. Once the job request submitted by the user is completed, the requirements definition is removed from the pool. The implemented system is customized for key search applications and hence a uniform requirement of resources is assumed. The proposed resource manager is not implemented.
3.2.1 Requirements Definition
A common protocol is used in expressing resource requirement and advertising resource availability. A user wishing to submit a job to the system has to specify certain attributes of the workstations he is targeting to use. The specifications, which are attribute value pairs, are translated into an XML message and sent to the server. Front-end tools or XML editors can be used as a user interface to construct the message. The following attributes can be specified:
Type This indicates the type of machine required to perform the job. The default is workstation. This attribute can accommodate different devices, if used in future.
Application Name The accompanying application executable or application name, for which the request is submitted.
Keyboard Idle Time The time in seconds of inactivity on the keyboard, before job processing. This value can be used as the default, if not specified by the workstation user.
Mouse Idle Time - The time in seconds of inactivity on the mouse, before job processing. This value can be used as the default, if not specified by the workstation user. If mouse and keyboard idle times are specified, both conditions will have to hold true.
Memory Minimum physical memory in megabytes to be present on the workstation to process this job.
Hard Disk Space Minimum hard disk space on the workstation to process the job.
CPU speed Minimum CPU clock speed on the workstation for the job.
Architecture The processor architecture, for example INTEL, on the workstation
Operating System The job executable submitted may be operating system specific, example value is SOLARIS251.
For an attribute that is unimportant to match, a null value can be specified. Attributes can have comma-separated values, to allow for multiple values. A sample of proposed XML structure for the requirements definition is illustrated in Figure 7.
The XML structure below gives the user the flexibility to specify a number of machines for a particular configuration. One can have multiple configurations for operating systems or architectures by writing out multiple records for a single application. The minimum and maximum tags can be added other nodes as well, as appropriate.
10
SOLARIS251
INTEL
750 Mhz
100 MB
32 MB
64 MB
900 secs
900 secs
Figure 7. XML structure for Job Requirements
The matchmaking algorithm will take as input an XML configuration file with values pertaining to the peers system. An XML schema for the same will be used to impose the specific data structure in constructing the message on the peer. For all non-null values, matching of values will be done. If the peer has the right specifications for the job, it will be assigned one. The user submitting the job can specify a minimum set of attributes that should match in value for a successful assignment. All current requirement definitions will be matched and the first available match will be honored. It is possible that some requirement definitions get preference because they get matched before others, leading to lack of resource allocation to job requirements posted later. In order to prevent this, a random matching order should be chosen each time the matchmaking algorithm initializes.
Job Scheduling and Load Balancing
The scheduler is responsible for computing a batch of jobs for the next peer. A batch job comprises one or many jobs. The number of jobs that a batch must contain is configurable for the application. A requesting peer can specify a number for the expected batch job. The job scheduler for the implemented system does a domain space breakup for the key search. The approach used is to use subsets of the key space by considering the limits of each byte (between 0 and 255) separately. The size of each subset is a quantity that is configurable and will determine the time each job takes to compute.
The scheduler first queries the job pool manager for pending jobs. A pending job pool is maintained in memory, which is periodically updated. An XML file is used to store job status and details, which is read and processed by the XMLFactory object to update the pending job pool. If there are no jobs that are pending, the scheduler computes a fresh batch of jobs for the peer. Job scheduling is done on a first come first served basis and offers some flexibility in terms of job batch size modification. After a peer returns results the testing module verifies the integrity and correctness of results, after which erroneous or fraudulent job results qualify the job to be reassigned. Those jobs get added on to the pending job pool.
Load balancing is an important design decision in distributed applications. The matchmaking algorithm addresses this issue partially, in assigning jobs to participants that satisfy minimal requirements recommended for the job. However, the resource manager does not perform a best-case analysis, but merely performs a requirements check. In future further load balancing can be provided by reassigning jobs to other peers should results not be received within a particular timeframe. This will prevent backlog of undone jobs over a period of time. Further, a peer can be assigned smaller or larger chunks of jobs in a batch depending on its processing capacity. This can be a request specification or an ascertained value after matchmaking. This will make sure that not all peers with varying capacities get assigned the same size of batch jobs.
The focus of this research study is fraud resilience in distributed computing applications. Results returned by all peers are tested thoroughly to detect incomplete work, incorrect work or fake results. This also implies that malicious and fraudulent users must be deterred, once caught. The server blacklists all peers that commit fraud and performs a check before assigning a new batch job to a peer. Over a period of time, voluminous data of peers can accumulate on the server, which may be an overhead to process each time. Another approach to storing this information is in a distributed fashion. Every peer is given an encrypted file, the key of which is known only to the server. The file contains crucial information about the peers identity and past history. This file is given to the server at the start of every session, which is decrypted, updated and encrypted again by the server. Absence of the file on the peer is also an indicator of untrustworthy users. In implementing the system, this distributed approach is not followed instead all peer information is stored on the server itself.
3.4 Peer Resource Usage
Volunteers who participate in distributed computing projects expect to contribute idle CPU time. Hence, it is essential to monitor system resource usage continually for some threshold values, in order to determine when to start processing jobs. Several approaches can be followed in this regard. Some distributed computing systems like SETI@HOME, use a screen saver, which the user installs on his computer. Like typical screen savers, this can be configured to launch after some time of keyboard and mouse inactivity. While the screensaver is running, the software starts processing jobs. As soon as the user returns, the screen saver and the software shut down, freeing up resources for the user. This approach is an unobtrusive CPU usage scheme for volunteer computing. Alternative approaches, which include more user participation, have Java applets running on some website the user visits via his browser. While the applet runs, jobs are processed, using the client system resources. Although not independent stand alone applications, applets are less invasive of a users personal data, if written with appropriate security features like sand-boxing.
The choice of Java for a volunteer computing application is restrictive in that one cannot write low level, platform-dependent code in Java. A possible alternative is to have C or C++ code and integrate it with the Java application using Java Native Interface (JNI). I have implemented system agents to monitor keyboard and mouse activity on win32 platform, in C++. The programs include Dynamic Link Libraries (DLL) for win32 platforms. For more information on DLLs, refer [13]. The programs indicate if they detect no activity for a certain period of time. That indication is used to trigger a worker thread to start processing jobs given by the server. The system agents now begin monitoring for activity on the keyboard or mouse. When the user returns, presumably when there is mouse movement or a key strike, the agents send a signal to terminate thread processing.
An important aspect of a break-off model such as above is the job-resumption after termination technique. Peer processing breaks-off periodically and is expected to efficiently resume in the next cycle, with minimal work lost. This means that the peer application should periodically record rollback breakpoints. Also, results of processed jobs have to be recorded at an optimal frequency, keeping a balance between I/O and processing speed.
The job-termination and resumption-model I have used is adapted to key search problems. The model is inspired by the concept of a semaphore, which is a built-in system data type, with an associated lock with locking and unlocking operations. Semaphores are used for synchronization between multiple processes, when in critical sections. In the resumption model, a single thread may be in critical sections when it is time to terminate. The semaphore concept is used to lock out the section, so that termination can occur only after the thread has exited the section and released the lock. Hence, in the destroy() method of the thread, the lock is checked continually to ascertain whether or not critical sections are exited.
In the course of job processing on the peer, critical sections may be identified as procedures used to communicate with the server to send results, wait for verification and server testing and receive the next batch job or an error report from the server. Another critical section to complete before thread termination is the process of recording results or rollback points in XML files. The CPU cycle time required for each of these procedures is lesser than that required for the actual job to process and can be acceptable for the duration of the critical section, even after the user returns.
The following pseudo-code illustrates the break-off model for the worker thread.
while (true)
{
xml_reader_next_job();
If (!job_to_process)
{
acquire_lock();
contact_server(results);
receive_message(message);
if (message == batch_job)
{
xml_writer(batch_jobs);
}
release_lock();
xml_reader_next_job();
}
--
--
--
xml_writer(found_ringer);
--
xml_writer(found_key);
--
acquire_lock();
xml_writer(job_status);
release_lock();
}
Figure 8. Peer Break-off Algorithm
Here, the worker algorithm is outlined. Once a worker thread is spawned, it endlessly reads jobs, processes them, writes results and updates the job status in the XML job file. If no undone jobs are present, the worker connects to the server, sends the results file and receives the next batch of jobs, after the server verifies the results. The xml_reader_next_job() method reads the existing job description file for the next undone job. The status attribute of all job records is read to ascertain if the job is processed or not. The xml_writer() writes the argument out to the appropriate file. All ringers and keys found are updated to the results file. The xml_writer(job_status) call will update the status of the current job as completed.
The break-off model is as follows. The critical sections in the algorithm, which have to be completed before termination, are indicated in red. Just before the thread enters these sections, a lock is acquired on a semaphore like variable. On exiting, this lock is released. This will ensure that these tasks are completed before termination, as in the destroy() method of the worker thread, a check on the lock is done continually until it is released. This way, on the next cycle, there will be minimal duplication of work, as server communication will have to repeat if it was terminated half way through and a job will have to be re-processed if the status update process was terminated previously. For resumption of job processing, the next undone job will be started with. They key is to have an optimal size for a single job, as the maximum work lost is one job. After much experimenting, I realized that a five-minute packet was reasonable.
Chapter 4
Fraud Resilience
4.1 Motivation
The system design discussed so far addresses functionality such as resource management, scheduling and load balancing in a heterogeneous network of participants. A crucial feature of distributed computing systems is fraud resilience. Volunteer computing models like SETI@HOME have experienced fraud by participants, where in users try to gain credit for work they did not do. Sometimes users tweak the application software with an intention to gain better results, but unknowingly disrupt accuracy and integrity of results. This accounts for false results and incomplete jobs. Commercialized systems are designed with payment schemes where in users can get paid for their contribution of CPU time. Here too it is imperative that the application is robust enough for results to be credible. This research study tries to address this issue and proposes a scheme that can be deployed for key searches. The security model discussed includes fraud resilience techniques and an authentication protocol. The fraud resilience model is implemented and tested for empirical results, which establish its effectiveness. A detailed analysis of the security model follows.
Cheat Resistant Scheme
4.2.1 Introduction
This scheme detects whether or not the user has indeed performed the computation and the results returned are fake or fabricated by the user. The algorithm is based on a scheme in [20]. Formally, three key elements can be identified in our distributed system:
A Function f defined on a finite domain D. In our case, f is the Tiny Encryption Algorithm (TEA) [25] cipher, which takes a key from domain D, and converts plain text (P) to cipher text (C). Hence, the objective is to evaluate f on all k that belong to D. The server distributes the computation by partitioning the domain D into subsets Di. The evaluation of f on Di is assigned to participant i. In our system, D = [0, . . ., 232 1] and f(k) = TEAk(P).
A Screener S. The screener is a program that screens results produced after applying the function f to all keys in domain Di. Every participant has the screener program, which ascertains the results to be given to the server. After a key has been tested, if the result matches the cipher text expected, the screener knows that the key is found. Hence, the screener takes as input a pair of the form (k; f(k)) for all k that belong to Di, and returns a string s = S(k, f(k)). In our example, S is a function that compares f(k) to C, where C is the Cipher Text. If they are equal, S(k, f(k)) = k, otherwise there is no result worth signaling to the server and S returns the empty string. An assumption made here is that the screener program does not add significant overhead to the computation.
A Verification function V. The Verification Function is performed by the server. Screeners from all participants return the strings after the computation of S(k, f(k)) for all keys in their domains. If the key is claimed to be found by a participant, the server verifies the correctness of k by performing f(k) and comparing the result to C.
In this basic model, the screener S and the verification scheme V are the same for all participants. For the purpose of verifying the work of individual participants, the model is modified to give the server the ability to customize S and V for each participant.
Customized screener. Rather than a common screener S, the server gives a unique screener Si to every participant. The server also generates a secret key Ki. The screener has the image( of the secret key Ki, while the key Ki is known only to the server. The key stores secret information associated with the peer, and is used to verify the work of participant i.
Customized Verification scheme. Similarly, the verification scheme V is customized for participants. We re-define V as a function of two inputs: a string s from participant i, and the secret key Ki. The result string is verified if it contains the image of key Ki that the server assigned to that peer earlier. In other words, not only is the server looking for the key to TEA, but is checking on completeness of computation by looking for Ki image in the result.
4.2.2 Ringer Scheme
The Ringer Scheme detects job evasion by cheating participants. In order to explain the ringer scheme, I distinguish the following three stages of the distributed computation.
Initialization: The server decides on a partition of the domain into finite subsets Di. The server generates a screener Si for each participant, and a key Ki to go with it. All the keys are kept secret. The key Ki produced individually for each participant can be implemented with ringers. The concept of ringers is simple. In the domain Di of a participant, the server selects a set of n values, dj (every dj belongs to Di), which are evenly distributed over the range and are randomly selected. These are ringers. Hence, the set of ringers make the secret key Ki. In other words, Ki = {r1,., rn}, where all r are ringers. They act like milestones in the domain Di. The server uses a one-way hash function to compute the images of these ringers for each participant. The hash function h, takes as input the cipher text (C), computed by applying the ringer ri to f(P). The set of ringer images, h(ri) where ri belong to Ki, are given to the screener, customizing it for that participant. Each participant then receives his share Di of the domain, a program performing the function f and the screener Si.
Computation: For every input dj that belongs to Di, participant i is required to evaluate f(dj), after which the cipher text produced is hashed using the same hash function h. The result produced is given to the screener Si. Since the screener knows what hash images, h(ri), to look for, upon finding one, it concatenates the key whose hashed image matched to string si, which is eventually sent to the server for verification. The screener will also be given the hash of expected cipher text, if found. Hence the screener can concatenate all relevant result strings into si, which is returned to the server at the end of the computation. To summarize, the server gives a set of hashed images to the screener and expects the set of ringer keys that map to the hashed values, in return. The strength of this scheme will now rest on the hash function. A collision free hash function, which is infeasible to reverse, should be used so that a malicious user cannot get to the key values if he has access to the hashed images. Should the hash function be weak, in that the user can compute the text that was hashed to produce an image, he still cannot get to the ringer, since that text would be the cipher text produced with the ringer and function f, in our case, TEA. The process of getting to a key from a TEA cipher text is obviously very difficult to accomplish, hence the distributed system. This will compel him to try every key in the domain Di to get all the ringers. Since the hashed values are computed with the cipher texts of the chosen ringer keys, the key space assigned will get searched in an attempt to find the ringers.
Verification: The server computes V(Ki, si) to determine the correctness and completeness of the result returned by participant i. In our case, the verification function will check for the completeness of the set of ringers returned by the screener. The Verification process will map the ringers to the set it has stored for that participant and only if all are present, will the job by the participant be verified. Should a successful key be announced, the verification function will validate the correctness of the key by performing f(k).
Additional security can be achieved by overlapping user domains Di for different users and matching results over common data sets. For the purpose of implementation, the algorithm to select ringers in a domain Di uses a random number generator to produce bytes in the range of 0 and 255. The lower and upper limits of domain Di, are represented as x bytes, where x is the size of the key in bytes. Each byte can have a value between 0 and 255. In specifying a domain subset Di, one will have to provide a lower limit and an upper limit for each individual byte. In searching the space, the approach used is to search every combination of the x bytes, with individual bytes in their respective ranges. Hence, a logical representation of a ringer is a collection of x values in the range for Di.
The cheat resistant scheme described above prevents malicious users from sending results they did not compute. This is accomplished by using a sound one-way hash function to compute ringer images for a participant. A user who is reverse-engineering application code, may find the number of images in the screener program, but due to the irreversibility of the hash function, cannot predict the ringers. Any results sent to the server, will not be accepted without the screener output string si containing the ringer images, which compels the user to perform the computation over the entire domain.
4.2.3 Obfuscating Screener Code
4.2.3.1 Rationale
The proposed model is irreversible and will keep a malicious user from finding out true ringers. However, it does not keep one from guessing what the ringers would be and trying to reverse engineer the software, in order to manipulate results. If individual job packets are small subsets of the key space, guessing ringers successfully may not be impossible. A user can attempt to pre-empt job processing and send results with guessed ringers. He can attack the application, trying to change code and behavior. One can argue that a malicious user, who has figured out how to communicate with the server and the protocol for sending results, can manually modify result files with guessed ringers and send out the fake results. A possible solution to an attack like this is to encrypt the result files with a secret key to make sure it is inaccessible to users. Each time the application updates result files, they are decrypted, modified and encrypted again. Due to time constraints, that part of the fraud prevention model is not implemented.
Coming back to the possible attack on the software portion that writes ringers out to result files, we discuss the second phase of the fraud resilience scheme. The server gives different screener versions to peers. The screener application screens all key hash images and tries to locate ringers. On finding one, it writes it to the result file. Hence, the screener can be subject to attacks by malicious users, more than other components. A user attempting to send fake results with guessed ringers is likely to tamper screener code. To combat this, the server maintains several versions of the basic screener program. The versions are different in some superfluous lines of code added to the program. At the highest level of security, a single user will be given different versions each time, which makes reverse engineering attempts harder to succeed each time. The screener application code is obfuscated using some tricks, described in the next sections, to make the code difficult to comprehend, should it ever be de-compiled.
4.2.3.2 Techniques
The rationale in the versioning scheme of the screener application is to contradict the good software engineering practices of writing readable code. Some of these practices are:
Use meaningful data variables
Avoid frequent jumps and spaghetti code
Modularize and use sub-routines
Choose data structures that make the program simple
By using several techniques simultaneously which do an opposite of the afore-mentioned, one can produce quite unreadable code, which is very tedious to make sense of. Following is a discussion of the details of techniques proposed along with ways to scale the algorithms for many versions.
Variable Re-composition
Adapted from a scheme to solve the problem of malicious hosts in paper [12], variable re-composition is a technique wherein all variables used in the program are collected and their data contents redistributed in bits and parts into new variables. The idea is to confuse the reader with complex data structures, instead of simple ones, which contain data belonging to different original variables. In places where that data is accessed in the program, variable references are substituted with functions that re-arrange data to the original order. This technique can be applied to native data types as well as objects. To complicate variable re-composition, one can introduce new data and mix it up with the original, in the re-composed variables. The new data is not used in the program, but makes it difficult to identify useful data parts in a complex data structure. This technique is scalable, as the order of re-arrangement can vary from one version of the obfuscated program to another. Also, the dummy data added can change for variation.
In the following code snippets, I illustrate this scheme with different data types.
Consider a case where there are three string variables, bestshop, flowers and wallet, each containing three characters. We can redistribute the strings in two variables v23 and v19, in a random order, as shown in figure 9.
Figure 9. Variable Re-composition for Strings, Source: [12]
Similarly, for integers:
int i= 0 ;
int j = 1;
can be replaced by:
int i=0;
int j=1;
Object[] v67 = new Object[10];
v67[2] = new Integer(i);
v67[9] = new Integer(j);
v67[0] = new Integer(678);
v67[1] = new Integer(0);
--
--
Figure 10. Variable Re-composition for Integers
As shown in the above figure, one can hide meaningful data, like integers i and j, in an array of objects and fill dummy data to confuse the reader.
Complex Expressions
Another technique to make code less readable is to substitute conditional branch constructs with runtime, data-dependent switch-case statements. This construct allows the use of expressions to evaluate a condition and branch. If simple expressions are substituted with complex, hard to read ones, it will be difficult to not only predict branching conditions, but also direction of branch.
Replace procedure calls with body
Writing modular code in subroutines makes it easy to understand the division of functionality in a program. For the purpose of obfuscation, one can replace modular code with a large block of code, which is difficult to analyze. Adding dead code is a trick that may be circumvented by data flow analysis techniques. In adding dead code, one must be careful to produce fake results in it, which may not be used eventually, but appears to be contributing to the functionality of the program.
4.2.3.3 Example of Obfuscated Code
The following code snippets illustrate a simple Java class before and after applying the afore-mentioned techniques.
public class Mess
{
public static void main(String[] args)
{
int i = 2;
String str = "Hello";
int j = 5;
int k = 1;
if (str.length() == 5)
{
str = "myString";
} else if (str.length() == 2)
{
str = "";
} else if (str.length() == 1)
{
str = "1675.9";
}
}
}
Figure 11. A simple Java class before obfuscation
In Figure 12 the above Java class is obfuscated with the techniques discussed earlier. In particular, the strings str and myString are re-composed in character array c10. The order used to distribute the characters is simple; alternate characters belong to a string in c10. The function tt() converts the strings back to their original orders. The function ttup() updates the character array c10 after any of the strings are modified. The if-then-else conditional construct is also replaced with a switch-case.
public class Mess
{
public static Object[] in78 = new Object[10];
int hh = 10;
public static char[] c10 = new char[50];
public static Object tt(char[] cc, int ii)
{
if (ii == ((Integer) c1000(new Integer(1), null, null, null)).intValue())
{
char[] cn = new char[15];
cn[0] = cc[1]; cn[1] = cc[3];
cn[2] = cc[5]; cn[3] = cc[7];
cn[4] = cc[9];
return (new String(cn));
}
if (ii == (((Integer) c1000(new Integer(1), null, null, null)).intValue() + 1))
{
char[] cn = new char[15];
cn[0] = cc[0]; cn[1] = cc[2];
cn[2] = cc[4]; cn[3] = cc[6];
cn[4] = cc[8]; cn[5] = cc[10];
cn[6] = cc[12]; cn[7] = cc[14];
return (new String(cn));
}
return new String();
}
public static Object c1000(Object i1, Object i2, Object i3, Object s)
{
if ((((Integer)i1).intValue() == 1) || (((Integer)i2).intValue() == 1) || (((Integer)i3).intValue() == 1))
return (new Integer(1));
if (i1 != null)
return (new Integer((((Integer)i1).intValue() - 1) + (((Integer)c1000(new Integer(1),null,null,(new String()))).intValue())));
if (i2 != null)
return (new Integer((((Integer)i1).intValue() - 1) + (((Integer)c1000(null,new Integer(1),null,null)).intValue())));
if (i3 != null)
return (new Integer((((Integer)i1).intValue() - 1) + (((Integer)c1000(null,null,new Integer(1),null)).intValue())));
if (s != null)
return (new String());
return new String();
}
public static void ttup(Object o, int ii)
{
int i = 0;
for ( i = 0 ; i<((String)o).length(); i++)
{
c10[i+1] = ((String)o).charAt(i);
}
c10[i+1] = '\0';
}
public static void main(String[] args)
{
c10[0] = 'm'; c10[1] = 'H'; c10[2] = 'y'; c10[3] = 'e';
c10[4] = 'S'; c10[5] = 'l'; c10[6] = 't'; c10[7] = 'l';
c10[8] = 'r'; c10[9] = 'o'; c10[10] = 'i'; c10[12] = 'n';
c10[14] = 'g';c10[11] = '\0';c10[16] = '\0';
in78[0] = "null"; in78[1] = "myString"; in78[3] = "987";
in78[2] = ""; in78[4] = new Integer(Integer.parseInt(((String)in78[3])) + 688);
in78[5] = "HashFile1.txt"; in78[6] = new Integer(2);
in78[7] = new Integer(1); in78[8] = "Hello";
in78[9] = new Integer(5);
switch(((String)tt(c10,1)).length()) //== ((Integer)in78[9]).intValue())
{
case 15: in78[8] = tt(c10,2);
ttup(in78[8], 77);
break;
case 2: in78[8] = in78[2];
ttup(in78[8], 9);
break;
case 1: in78[8] = in78[4];
ttup(in78[8], 0);
break;
}
}
}
Figure 12. Obfuscated Java Class
4.3 Authentication Protocol
In a distributed computing scenario like ours, authentication of participants is important. Users can misuse the system by posing as someone else and gain credit for work they did not do. Although not implemented, a proposed security protocol to combat this situation follows.
The server creates digital certificates for each participant at the time of registration and profile creation. This certificate will contain information that will uniquely identify the participant. We assume a public/private key pair for the server and every participant. The keys are used to encrypt and decrypt the digital certificate. At the time of transmission of results by the participant to the server, a protocol for authentication takes place for the exchange of the digital certificate. A handshake protocol similar to SSL [24] could be a possible implementation. Alternatively, the entire session can also be encrypted with a session key decided by the server and the participant for every session using a scheme similar to the Diffie-Helman Key exchange.
When a peer connects with the server, it transmits its digital certificate to the server. The server in turn decrypts the certificate using its private key and authenticates the peer. If the certificate is fabricated, it will not decrypt with the private key of the server. Once authentication is done, the peer and server follow a protocol to determine a session key to encrypt messages in that session.
Chapter 5
Results
Test Environment
The implemented system was tested on a local area network comprising 3 PCs. The testing platform was Windows 2000. The machines had Intel Pentium II processors, at least 128 MB RAM and 933 Mhz clock speed.
The system was tested for a Tiny Encryption Algorithm (TEA), 32-bit key. A 32-bit key can be found in a reasonable time frame, which makes testing for results feasible. A known plain text and cipher text pair was used throughout the system on which an exhaustive key search was performed. Results measured were for three peers in tandem, which were then scaled to predict results for a 64-bit key.
The tests that follow provide empirical data of system performance, measured in milliseconds of response time. Some system parameters are varied and response times recorded.
5.2 Ringers
The ringer scheme has several parameters which can be varied to test performance and efficiency, like the number of ringers in a job packet, choice of hash function and number of screeners. The following tests were performed to measure the processing time by varying number of ringers. The hash function used was Tiger [22]. All tests were performed with the same batch job, which comprised four jobs. Each of the jobs specified a subset of the 32-bit key to search. The batch job searched a total of 230 keys, a fourth of the total search space. The following table contains the processing times with varying number of ringers for the same batch job.
RingersTime in seconds472966739287526Table 2. Ringer Number Tests
The results indicate a 3.15% increase in processing time when ringers are increased from 4 to 8. In other words, the increase in time per ringer is 0.78%. If we consider the increase in time for 6 ringers from that of 4, we get a 0.65% increase in time per ringer.
Server Performance
The server is multi-threaded and it spawns a new thread for every client request. Server response time is key to the performance of the system. Server response times are measured for the job-scheduling phase. The following tests were conducted with multiple client requests for the same size of batch jobs. Concurrent client requests were sent to the server and average response time measured for each case. Like in the previous case, each batch job comprised 2 jobs to search subsets of the key space. In all cases, 4 ringers were computed for each job.
ClientsAverage Response Time (milliseconds)21532.551692.483103.5Table 3. Server Scheduling Tests
The above results indicate a 102.5% increase in server response time when concurrent client requests are increased from 2 to 8.
Analysis of Results
A good approach to implementing the parallel cipher algorithm and hash function is as an executable in a language like C. Performance times of C and Java programs can be dramatic for low-level bit wise operations, such as those in TEA. Another important consideration is the choice of hash function. I have experimented with SHA1 and Tiger [22]. I found the latter to be a faster hash function. For an application like an exhaustive key search, it is important that the work amount is minimized for each cycle.
The number of ringers chosen, do not effect the performance time of the peer system much. Moreover, more ringers will provide better coverage of the domain. As an example, a 30-minute job with 8 ringers will approximately cover 3.7 minutes of work per ringer. As mentioned previously, the increase of time per ringer is approximately 0.7%.
Chapter 6
Conclusion and Future Work
6.1 Concluding Remarks
The results of out test environment corroborate the efficiency of the ringer scheme in compelling users to complete their jobs. I have implemented a subset of the proposed model as a test base for the fraud resistant scheme. A complete implementation will enable thorough testing of resource management techniques as well. The Ringer Scheme is a generic model for setting hidden milestones in any large computation. It is a model that can be applied to any application, which consists of computations that produce unique results that have some dependency on the input data. Should redundant results be produced, hash images will be redundant, giving significant clues to the user regarding the milestones.
For performing exhaustive cryptographic key searches, using a separate hash function may be redundant if the cryptographic function is a strong, collision-free one-way function. However, for the purpose of demonstrating a general security model, implementing a hash function is necessary in this research project. Java offers a gamut of technologies for distributed web services, many of which are XML compliant. This research was also about studying the use of Java and XML in developing a distributed system.
Future Work
6.2.1 Server Scalability
Volunteer computing applications have the potential to scale to millions of Internet users. A potential bottleneck in the system can be server functionality. Distribution of server functionality over a hierarchical structure is an area of future research for this system. A possible implementation could be to have a hierarchy of system managers with the network partitioned amongst those at the lowest level. Each system manager monitors resources in its domain and performs job scheduling, load balancing, testing and verification of results. At the highest level, overall system performance is monitored. A break up of functionality like this will help make the system scalable and manageable.
6.2.2 Inter-peer communication
Inter-peer communication is a step in the direction of peer-to-peer systems. The idea is to give peers enough functionality to request and respond to other peers. Some applications may require sharing of data and results amongst peers, which calls for searching and querying online peers for specific content. However, performing optimal resource management and load balancing will be challenging in a peer-to-peer scenario.
6.2.3 Payment Schemes
The idea of using ringers to quantify work done holds promise for commercial systems. In [14], a probabilistic theory is given to suggest a scheme to motivate users to complete their tasks for financial gain and deter them from cheating by penalizing them for doing so. The proposed ringer scheme can probably be integrated with the same.
Appendix A: Annotated Bibliography
[1] Andrade etc., (2003). OurGrid: An Approach to Easily Asse m b l e G r i d s w i t h E q u i t a b l e R e s o u r c e S h a r i n g . I n t h e P r o c e e d i n g s o f t h e 9 t h W o r k s h o p o n J o b S c h e d u l i n g S t r a t e g i e s f o r P a r a l l e l P r o c e s s i n g .
[ 2 ] A n d r e w C h i e n e t c . , ( 2 0 0 3 ) . E n t r o p i a "!: A r c h i t e c t u r e a n d P e r f o r m a n c e o f a n E n t e r p r i s e D e s k t o p G r i d S y s t e m . J o u r n a l of Parallel and Distributed Computing, 597-610.
[3] Andy Oram OReilly & Associates, Inc., Sebastopol CA (March 2001). Peer- To-Peer Harnessing the Power of Disruptive Technologies.
[4] Baldeschwieler and R. Blumofe and E. Brewer (1996). Atlas: An Infrastructure for Global Computing. In Proceedings of the Seventh ACM SIGOPS European Workshop on System Support for Worldwide Applications.
[5] Baratloo etc., (1996). Charlotte: Meta Computing on the Web. In the Proc. of the 9th Int'l Conf. on Parallel and Distributed Computing Systems ({PDCS}-96)
[6] Baratloo etc.,(1999). Mechanisms for Just-in-Time Allocation of Resources to Adaptive Parallel Programs. In Proceedings of International Parallel Processing Symposium (IPPS/SPDP).
[7] Basney etc. (1997). Mechanisms for High Throughput Computing. SPEEDUP Journal.
[8] Bernard and Simantic. A Decentralized and Efficient Algorithm for Load Sharing in Network of Workstations.
[9] Condor Project Homepage, HYPERLINK "http://www.cs.wisc.edu/condor/" http://www.cs.wisc.edu/condor/
[10] Dreamtech Software Team (Author), Published by Hungry Minds, Inc., NY (2002). Peerto-Peer Application Development: Cracking the Code.
[11] Foster, Kesselman and Tsudik (1998). A Security Architecture for Computational Grids. (ACM) Conference on Computer and Communications Security, 83-92.
[12] Fritz Hohl, (1997). An Approach to Solve the Problem of Malicious Hosts. In the proceedings of 4th ECOOP Workshop on Mobility: Secure Internet Mobile Computations.
[13] Glenn D. Jones (1997). A Short Tutorial on Writing a Win32 DLL. HYPERLINK "http://www.coopknow.com/papers.asp?paper=5" http://www.coopknow.com/papers.asp?paper=5
[14] Golle and Stubblebine. Secure Distributed Computing in a Commercial Environment.
[15] Leon Erlanger (2002). Distributed Computing: An Introduction. ExtremeTech, HYPERLINK "http://www.extremetech.com/article2/0,3973,11769,00.asp" http://www.extremetech.com/article2/0,3973,11769,00.asp
[16] Luis F.G. Sarmenta (1998). Bayanihan: Web Based Volunteer Computing Using Java. In the Proceedings of 2nd International Conference on World Wide Computing and its Applicati ons.
[17] Luis F.G. Sarmenta (2002). Sabotage-Tolerance Mechanisms for Volunteer Computing Systems. Future Generation Computer Systems, v-18, 561-572.
[18] Meyer, Hieneken and Popien (1995). Performance Analysis of Distributed Applications with ANSAMon. In the proceedings of International Conference on Open Distributed Processing (ICODP '95), 293-304.
[19] Navrat and Smolarova. Software Reuse: Principles, Patterns, Prospects.
[20] Philippe Golle and Ilya Mironov (2001). Uncheatable Distributed Computations. In Proceedings of the RSA Conference 2001, Cryptographers' Track.
[21] Rao and Neuman (1993). Resource Management for Distributed Parallel Systems. In the proceedings of 2nd International Symposium on High Performance Distributed Computing
[22] Ross Anderson and Eli Biham (1996). Tiger: A Fast New Hash Function. Fast Software Encryption, LNCS 1039, D. Gollmann, Ed., Springer-Verlag, 89-97
[23] SETI@HOME: An Experiment in Public-Resource Computing
HYPERLINK "http://setiathome.ssl.berkeley.edu/cacm/cacm.html" \t "_blank" http://setiathome.ssl.berkeley.edu/cacm/cacm.html
[24] SSL-3.0 Specification HYPERLINK "http://wp.netscape.com/eng/ssl3/draft302.txt" http://wp.netscape.com/eng/ssl3/draft302.txt
[25] Wheeler and Needham (1994). TEA, a Tiny Encryption Algorithm. Fast Software Encryption, Second International Workshop Proceedings, Springer-Verlag, 97-110.
[26] XML Tutorial, HYPERLINK "http://www.w3schools.com/xml/default.asp" http://www.w3schools.com/xml/default.asp
Appendix B: Glossary
ARPANET - A wide area network that was the precursor to the Internet, created by the United States Defense Advanced Research Project Agency (ARPA), in 1969.
Bayanihan Project Bayanihan started at the MIT Laboratory of Computer Science and is based on the idea of volunteer computing, where participants all over the world can contribute to the system by visiting a web site with an appropriate browser.
Calypso A prototype software system for writing and executing parallel programs by providing a simple programming paradigm incorporating shared memory constructs, dynamic load balancing and fault tolerance.
Charlotte A meta-computing project based on a virtual machine model, which is a high-level platform independent system.
Checkpointing A mechanism used in the Condor project to enable a process to record its current state in the form of checkpoint files, which contain data and stack segments. This information is used by migrating processes to resume job execution after migrating to idle machines.
Condor A product of the Condor Research project at the University of Wisconsin-Madison, Condor is a specialized workload management system for compute-intensive jobs.
D a t a S y n a p s e A g r i d - c o m p u t i n g c o m p a n y . D a t a S y n a p s e s s o l u t i o n G r i d S e r v e r "! i s t h e o n l y p r o d u c t i o n - p r o v e n s o l u t i o n t h a t e x t e n d s a p p l i c a t i o n s i n r e a l t i m e t o o p e r a t e i n a d i s t r i b u t e d c o m p u t i n g e n v i r o n m e n t a c r o s s a p o o l o f n e t w o r k e d r e s o u r c e s .
D a t a E n c r y p t i o n Standard (DES) The most widely used encryption algorithm. DES is a block cipher, which performs permutations on blocks of plain text and produces cipher text of the same size.
Diffie-Helman key exchange A method used by two parties to agree upon a secret cryptographic key using an exchange of messages in the clear.
Entropia A PC grid computing company with solutions to tap the power of PCs in an enterprise network to process computationally intensive jobs for business and scientific applications.
Napster A peer-to-peer software application written and distributed freely on the web, targeted to share music files amongst users.
Parallel Virtual Machine (PVM) A software package that permits a heterogeneous collection of networked Unix and/or Windows computers to be used in parallel like a single computer.
RSA An encryption algorithm developed by Rivest, Shamir and Adleman. It uses a public-private key pair for encryption and decryption.
Sandbox A Java technology, which provides security from untrustworthy code, by restricting its memory access. A sandbox is used for security purposes when executing Java applets.
SETI@HOME - Search for Extra-terrestrial Life at Home is a distributed computing project that started in University of Berkeley in 1997. The project uses distributed resources to scan signals from the Arecibo satellite in Mexico for signals of extra-terrestrial life.
Secure Socket Layer (SSL) A security protocol developed by Netscape to transmit private documents on the Internet. Private key encryption is used to transfer data. Both Internet Explorer and Netscape browsers support SSL.
Semaphore A built-in system data type internally associated with a lock and a queue for process blocking purposes. Only two operations, one for acquiring the lock and the other for releasing it, are allowed on semaphores for process synchronization.
Secure Hash Algorithm (SHA) The Secure Hash Algorithm is a cryptographic message digest algorithm similar to MD4. It takes a message of length less than 264 bits and produces a 160-bit message digest.
Tiny Encryption Algorithm (TEA) A feistel type simple encryption algorithm that is often used to replace DES for encryption.
XSLT The Extensible Stylesheet Language Transformation standard by the W3C, XSLT, is a tree-oriented transformation language for transforming XML documents into simple text, HMTL or other XML documents.
( Bold face text found in Glossary
( The cheat resistance scheme uses ringers. For more information, refer to section 4.2.2.
( The Screener application is customized for peers and different versions are maintained. Refer to section 4.2 for more information.
( The image of the secret key is discussed in section 4.2.2
Fraud Tolerant Distributed Computing Shruti Parihar PAGE 2 PAGE 24
December 08th, 2003 PAGE 2
Peer thread
register
View
Job
progress
Install
app
xml factory
communication
Job pool
Worker
View
Controller
Model
Scheduler
DiscompServer
GlobalSocketPeer
GlobalSocketServer
GlobalSocket
PropertyLocator
XMLFactory
ResultViewer
System agents
DiscompPeer
XMLFactory
Screener
GlobalSocketPeer
GlobalSocketServer
User Interface Layer
Performance Layer
Communication Layer
Requirements pool
Pending job pool
Results pool
Resource mgr
Schedule mgr
Screener mgr
Testing factory
Server central thread
Xml read
Xml write
Screener
Worker
Peer central thread
Register
View results
Xml read
Xml write
Screener
Worker
Peer central thread
Register
View results
Resource mgr
Schedule mgr
Screener mgr
Testing factory
Server central thread
Users submitting requirements
server
peer
peer
PendingJobPoolMgr
RingerMgr
ScreenerMgr
VerificationFactory
Communication Layer
Data Layer
Job Layer
Worker
GlobalSocket
) * + , 5 6 7 P Q R S T U V W X s t u v ּЉ xvovgovo j Uj U j >*B*Uph 0J
j 0J Uj UmH nH u j UmH nH umH nH u 0J aJ mH nH u&j# >*B*UmH nH ph u mH nH u0J mH nH uj 0J UmH nH u 5CJ OJ QJ \^J CJ j U ( * - < = > V s V M % # $ $a$ $ @^@`a$ ^` k l 4m p , - . G H I J K L M N O j k l m p q j
>*B*Uph jv
Uj >*B*Uph j Uj >*B*Uph j Uj U j >*B*Uph 0J
j 0J U = 9 : ; < ? @ c d e ~ 0J mH nH uj 0J UmH nH u mH nH ujX
Uj >*B*Uph jb Uj >*B*Uph jl Uj U 0J
j 0J U 6 ) < 0
7 C A
3 . # $ % " # $ & ' ( ) * + F G H I ` a b { | } ͳ߭ v n j: Uj >*B*Uph jD Uj U j >*B*Uph 0J
j 0J UmH nH ujN UmH nH u j UmH nH umH nH u 0J aJ mH nH uj 0J UmH nH u &j
>*B*UmH nH ph u+ 5 6 7 9 : ; < = > Y Z [ \ _ ` o p q ߫菱 j 0J UmH nH u mH nH uj Uj >*B*Uph j& Uj >*B*Uph j0 Uj >*B*Uph 0J
j 0J Uj U;
)
*
+
-
.
/
0
1
2
M
N
O
P
c
d
e
~
ƾ { m j >*B*Uph j Uj U j >*B*Uph 0J
j 0J Uj UmH nH u j UmH nH umH nH u 0J aJ mH nH uj 0J UmH nH u &j >*B*UmH nH ph u mH nH u0J mH nH u *
0 1 2 4 5 6 7 8 9 T U V W Z [ | } ~ j Uje >*B*Uph j Ujo >*B*Uph j Ujy >*B*Uph 0J
j 0J Uj U j U = ! " # < = > @ A B C D E ` a b c s t u ƾ { m jG >*B*Uph j Uj U jQ >*B*Uph 0J
j 0J Uj UmH nH u j UmH nH umH nH u 0J aJ mH nH u&j[ >*B*UmH nH ph u 0J mH nH uj 0J UmH nH u mH nH u *
!
:
;
<
>
?
@
A
B
C
^
_
`
a
d
e
|
}
~
䲥 &j) >*B*UmH nH ph u 0J mH nH uj 0J UmH nH u mH nH uj Uj3 >*B*Uph j Uj= >*B*Uph 0J
j 0J Uj Uj U 4
, - . 0 1 2 3 4 5 P Q R S V W g h i j Uj >*B*Uph j Uj U j >*B*Uph 0J
j 0J UmH nH uj 0J UmH nH u j UmH nH u j UmH nH umH nH u 0J aJ mH nH u 0
' ( ) + , - . / 0 K L M N Q R e f g 礗 0J mH nH uj 0J UmH nH u mH nH ujr# Uj" >*B*Uph j|" Uj" >*B*Uph j! Uj U 0J
j 0J Uj! >*B*Uph 7. / = > 2 Z ; q 0 1 < # $ %
( ) * , - . / 0 1 L M N O R S e f g ͳ߭ v n jT&