Attachment 2 - Mock TO2 PWS - Software Development.pdf

Secure Tool Chain Challenge Problems CAPSS Sample TO 2 Performance Work Statement

1.0 Background

NIST promotes the U.S. economy and public welfare by providing technical leadership for the nation’s measurement and standards infrastructure. NIST’s responsibilities include the development of management, administrative, technical, and physical standards and guidelines for the cost-effective security and privacy of other than national security-related information in Federal information systems.

Many security weaknesses in Federal information systems stem from software security vulnerabilities present in current-generation software products. In advancing its mission objectives, NIST tracks software security vulnerabilities (in the National Vulnerability Database), seeks techniques for the measurement of security vulnerabilities, and also seeks techniques to reduce the impact and prevalence of security vulnerabilities in newly developed products or in new versions of existing products.

One approach to reducing the number of security vulnerabilities in software is to identify languages and software development tools that make it easier to create software with fewer security vulnerabilities, and to stimulate the development of new and better tools. While it is impossible to assure the total absence of security vulnerabilities in this way, it might well be possible to rule out specific, significant classes of vulnerabilities that today provide the basis for many serious exploits.

NIST is developing an empirical, competitive approach to finding the most effective and usable combinations of tools to produce software systems that are relatively free of exploitable vulnerabilities1.

The participants in the planned competition will implement software systems to solve challenge problems using software development tool chains (“tool chains”) of their own choosing, within specified time periods. The competition will apply time pressure to the software development process to increase the likelihood of security flaws; the objective of the tool chains will be to detect or prevent security flaws while still supporting quick-paced software development of applications having rich feature sets.

Through a competitive process, NIST seeks to stimulate the development of more effective tool chains.

Through the demonstration of security flaw avoidance in a time-constrained setting, NIST seeks to show that security can be improved without sacrificing time-to-market, and therefore to stimulate a wide-scale improvement in how security is provided in software products throughout the economy. The tool chains may include existing technologies (e.g., existing software libraries and frameworks, code generators such as lex/yacc, reusable source code, bug-finding tools), novel technologies, or any combination. The competition will aim to provide a level playing field for the application and measurement of the full spectrum of commercial and research software development/composition/reuse techniques. The competition will aim to attract the participation of teams of university students but will be open to all interested parties.

1 The competition described here is based on one of the ideas developed during the Designing a Secure Systems Engineering Competition (DESSEC) workshop run by NSF in 2010:

Secure Development Tool Chain

The winning team must build a tool that allows non-security-expert developers to rapidly build a significant application (a non-trivial piece of communication software, e.g., a minimal email server, or an online simple database serving multiple concurrent clients), with zero vulnerabilities as detected by an extensive public test suite.

2.0 Objectives

NIST’s Computer Security Division’s (CSD) objective for this tasking is the creation of a collection of software programming challenge problems and their associated test suites. The challenge problems will be suitable for a competition setting, i.e., they will describe objective functional and security requirements, and the complexity and difficulty of the challenge problems will be calibrated to place significant time pressure on even the most highly skilled software developers, using state-of-the-art tools, in the time available during the competition.

The associated test suites will subject participant software submissions to automated testing that produces a pass/fail score for each test case; a test suite will contain a number of test cases (a minimum is given below). The testing will include both functional tests (i.e., does the software being tested implement the required features) and security tests. The security tests will include both randomized fuzz testing and also problem-specific testing that probes areas of greater difficulty where mistakes are more likely, that can be inferred from the functional and security requirements.

The challenge problems and the associated test suites shall NOT be disclosed before the planned competition has completed, and they shall be marked FOR OFFICIAL USE ONLY until after the competition is held, after which they will be publicly posted by NIST.

This task order focuses exclusively on the generation of challenge problems and their associated test suites. The competition itself will be funded and conducted through other means.

3.0 Scope

NIST requires contractor support for the creation, refinement, coding, implementation, and testing of “challenge problems” in support of a time-constrained code development competition. Specifically, the contractor shall be required to:

1. formulate preliminary challenge problems,

2. brief preliminary challenge problems to NIST staff,

3. write draft documentation for challenge problems,

4. brief documented challenge problems to NIST staff,

5. update challenge problem documentation based on NIST feedback,

6. implement a solution to each challenge problem,

7. brief NIST on lessons learned through implementations,

8. implement a test suite for each challenge problem,

9. brief NIST on scoring based on the test suites, and update according to NIST feedback,

10. internally simulate a part of the competition (“mock competition”) by having selected staff implement a fresh solution to each challenge problem, under time constraints, and document the completeness of the fresh solutions and associated test scores, and

11. update the challenge problem documentation and test suites based on lessons learned in step 10.

This will be a hybrid Labor-Hour and Firm-Fixed Price Task Order.

4.0 Tasks

The contractor shall perform the tasks in 4.1 and 4.2 iteratively, in 2-week Sprints:

4.1 Challenge Problem Development (Labor Hour)

4.1.1 Preliminary Challenge Problem Descriptions – 1 to 2 Sprints

The contractor shall formulate at least 6 preliminary challenge problems. Each preliminary challenge problem shall describe a software component that should be implementable by a competition participant team comprised of 4 skilled software developers given a limited number of hours (no more than 8), and shall informally describe the interfaces (e.g., function prototypes, protocol message formats, files, file formats, signals) between that component and other components in a testing environment that is driven by a test suite.

The contractor shall formulate the preliminary challenge problems representing any of a variety of well-known software kinds, e.g., command-line programs, GUI applications, library functions, server processes, client-server applications, socket-based networking applications, system calls, kernel modules, browser plugins, web server plugins, scripts, mobile device apps, or other kinds of software as chosen by the contractor. It is not necessary for each challenge problem to be of a different kind, but the challenge problems shall relate to current real-world software development efforts, which span a variety of software kinds.

Each preliminary challenge problem shall be described by 2-3 pages of documentation in UNIX-style man pages, written and formatted using MS Word. Each man page shall describe the functional requirements of a participant implementation of the challenge problem (e.g., features, options, outputs). Each man page shall also include a section describing the security requirements that participant implementations must satisfy despite crafted malicious input produced by (other) components in the test environment that are driven by a test suite.

The preliminary challenge problems shall be formulated such that the interfaces between participant components and test suite components demonstrate a degree of complexity that requires participant components to carefully handle security concerns such as authentication, parameter validation, access control, data integrity, and information leakage in order to satisfy the documented security requirements.

The preliminary challenge problems shall be structured such that specific features can be made optional without disturbing the most basic logic of each preliminary challenge problem. The ability to include or exclude some features of challenge problems may be necessary in later steps of this Task Order to configure the difficulty of challenge problems based on experience with how long each one takes to solve.

In some cases, preliminary challenge problem descriptions shall discuss specific platform details and features (e.g., mobile device operating systems for apps). To the extent possible, however, preliminary challenge problem descriptions shall minimize the dependency on platform details.

Preliminary challenge problems shall not require that participants use specific programming languages in their implementations. Preliminary challenge problems shall, however, describe any required interface bindings in terms of well-known programming languages, such as Java, C, or C++.

Acceptance criteria: NIST will accept each preliminary challenge problem description based on its clarity, the richness of the security concerns that are realistically represented in the problem description, the appropriateness of the problem’s size relative to the competition’s time constraints, and the configurability via optional requirements. NIST may conditionally accept a preliminary challenge problem with the statement from the contractor that NIST feedback will be incorporated.

If some of the preliminary challenge problems are not accepted, the contractor shall provide alternate preliminary challenge problems that meet the acceptance criteria. The alternate preliminary challenge problems shall all be delivered at the same time, within one month.

4.1.2 Draft Challenge Problem Documentation – 1 Sprint

The contractor shall refine the preliminary challenge problems based on NIST Contracting Officer’s Representative (COR) feedback and shall then generate complete, but still draft, documentation for the 6 challenge problems, also formatted as UNIX-style man pages. The challenge problems shall be documented to a level of detail that enables skilled computer scientists to read them and development implementations that satisfy them. In order to facilitate swift implementation of challenge problems, the contractor may include a section on “IMPLEMENATION HINTS” to help participants move quickly through standard programming details.

The man page in Appendix A is an example of the desired level of detail and clarity for a challenge problem’s documentation. The example in Appendix A is provided only to help clarify the intent of this Task Order and shall not be proposed as one of the challenge problems (NIST may wish to use this example in marketing materials or presentations relating to the competition).

The contractor shall formulate at least 6 draft challenge problem descriptions to the level of detail and clarity in the example provided in Appendix A. The contractor shall present them to NIST staff. During the presentations, the contractor will receive NIST feedback to incorporate into subsequent, more mature versions of the challenge problems.

Acceptance criteria: NIST will accept each of the 6 draft challenge problem description based on its clarity, the richness of the security concerns that are realistically represented in the problem description, the appropriateness of the problem’s size relative to the competition’s time constraints, and the configurability via optional requirements. NIST may accept a draft challenge problem conditionally, with the condition being that the contractor shall incorporate specific NIST feedback.

If a draft challenge problem is not accepted, the contractor shall provide an alternate draft challenge problem that meets the acceptance criteria within one month. The contractor is required to obtain COR approval of 6 challenge problems total.

4.1.3 Develop Solutions for Challenge Problems – 4 to 8 Sprints

The contractor shall develop solutions for each of the challenge problems already documented. The contractor shall present the implementations to NIST staff and demonstrate the operation of all of the challenge problem implementations. The contractor shall update the associated documentation (man pages) for the challenge problems as needed, based on experience with the implementations, and based on consultation with NIST. The implementations shall be documented and shall be of a quality suitable for public posting after the competition has been completed. The contractor shall employ languages and tools in the implementations that are freely available. If an implementation requires a particular platform configuration, the contractor shall document the configuration steps. If the implementation requires particular input files in order to execute, the contractor shall provide samples.

Acceptance criteria: NIST will accept each challenge problem implementation and associated documentation based on whether implementation runs correctly, produces understandable and correct output, and implements the functional and security requirements described by the corresponding challenge problem man page, and based on the clarity of the associated documentation.

4.2 Test Suite Development – 4 to 8 Sprints (Labor Hour)

The contractor shall develop, for each challenge problem, a test suite for assessing implementations of the challenge problem. A test suite shall function in an automated manner and shall require minimal human operator interaction. A test suite shall be configurable to test implementations of the corresponding challenge problem with the various optional components identified in the associated challenge problem documentation either enabled or disabled. The eventual competition will allow participant software submissions to be created using any programming languages or software generation techniques. The test suites shall refrain from performing source code analysis on participant software submissions, but may perform binary analysis, and may analyze runtime behavior.

Each test suite shall include both functional and security testing. Each test suite shall output, for each program under test, a collection of test results that briefly summarizes the results of each test performed (e.g., “integer overflow of key in –a option”) and indicates whether the program passed or failed the test. The test suites shall be documented and shall be of a quality suitable for public posting after the competition has been completed. The contractor shall employ programming languages and tools in the test suite that are freely available.

The functional tests shall comprise at least 12 separate pass/fail tests that cover the specified functionality of a participant’s software submission.

The security tests shall include fuzz testing of a participant’s software submission’s interface. See, for example, “An Empirical Study of the Reliability of UNIX Utilities” by Barton P. Miller, L Fredriksen, and B.

So. The fuzz tests shall be structured so that randomly-generated input data can be saved and later re-run for regression testing purposes or reused across multiple participant submissions. The fuzz tests shall be configurable to limit the time spent fuzz testing.

The security tests shall also include at least 12 separate pass/fail tests that check that the participant software submissions faithfully implement the required security policy statements in the challenge problem man pages. The security tests shall furthermore probe likely problem areas based on an understanding of the feature set of each challenge problem.

The contractor shall deliver both software implementations of the test suites and associated documentation describing how to configure and run the test suites. The contractor shall present and demonstrate the test suites to NIST staff. The contractor shall demonstrate the test suites running for all of the challenge problems and shall show the resulting test outputs. For each challenge problem, the contractor shall show both an implementation that passes the tests, and an implementation (perhaps an earlier version) that fails some of the tests. The contractor shall update challenge problem implementations and documentation as needed to respond to any problems uncovered by the test suites. During the presentations, the contractor will receive NIST feedback to incorporate into subsequent, more mature, versions of the test suites.

Acceptance criteria: NIST will accept each test suite based on whether it operates correctly, covers the functionality of each challenge problem, covers the security requirements of each challenge problem, implements fuzz testing, and produces understandable output.

4.3 Challenge Problem and Test Suite Validation (Labor Hour)

The contractor shall simulate the competition at NIST Gaithersburg or in a virtual meeting, document the results, and report the results to NIST. The internal simulation shall be based on simulated participant teams (1 per challenge problem at minimum) drawn from the contractor’s staff. Each team shall be comprised of 4 skilled software developers who are unfamiliar with the challenge problems.

The actual competition will announce the software kinds to be developed (i.e., a web browser plugin, a command line utility, etc.) months in advance so that participant teams can bring appropriate developer skills to each round of the competition. In this task order, the contractor shall simulate such prepared teams by choosing staff that have appropriate background in the software kinds that will be developed during the timed implementations of the challenge problems. This may require several distinct teams to cover all the challenge problems.

The contractor shall conduct the simulated tests using the challenge problems and use the associated test suites to score the implementations developed by the simulated teams under time pressure. Each simulated team shall be given no more than 8 hours to implement each challenge problem (and may be given less at the discretion of the contractor) and shall have no knowledge of each challenge problem before the timing starts. The contractor shall provide the man page for a challenge problem to the simulated team at the start of the timed period, and not before.

During the time when the simulated team is implementing a challenge problem, the contractor shall document, to the extent feasible, which functional or security areas of the challenge problem are relatively time-consuming for the team; this information may be used subsequently to configure the optional elements of the challenge problem.

The contractor shall run the test suites on the implementations developed by the simulated teams immediately upon completion of the implementations. The contractor shall document the progress of each test (start times, end times, test results, issues uncovered), and shall present the outcomes to NIST in a written report and briefing. The contractor may use multiple teams concurrently.

Acceptance criteria: NIST will accept each validation exercise based on whether the test protocol was honored (the correct time given, no advance information on the challenge problem, etc.), on the completeness and clarity of the test documentation, and on the successful scoring of each implementation using the associated test suite.

4.4 Planning and Reporting (Firm-Fixed Price)

4.4.1 Management Meeting

All work to be accomplished under this task order shall be managed through an Integrated Project Work Plan. NIST will approve the Project Work Plan or provide comments for revision within five (5) business days of delivery. After the contractor accepts and incorporates the comments, the Project Work Plan will be considered the baseline for the work effort. The contractor shall provide status on the Project Work Plan monthly and send the updated Project Work Plan to the project stakeholders, to include the Government COR, Technical Lead and Project Sponsor (optional), as well as the contractor’s Task Order Manager and Key Personnel (optional) at least 3 days prior to the monthly status meeting. The Project Work Plan shall contain government dependencies highlighted in yellow. Updates to the plan that do not impact the critical path can be resolved at the monthly status meeting as a function of the project plan. Changes that extend the period of performance or impact product delivery (i.e., removing PWS defined deliverables or adding new deliverables) will be addressed through mutually agreed upon contract modification actions.

Figure 1: Government Work Break Down Structure (WBS)

The contractor shall provide the initial Project Work Plan at the meeting kickoff. Also at the kickoff meeting, the contractor shall provide their critical path analysis of the work plan and the decomposition of the government Work Breakdown Structure (Figure 1) through levels 3-5 where appropriate. The Project Work Plan shall include an identification of contractor resources, deliverables and completion dates, sequence of events, start dates, and duration for each activity.

The completion dates established in the baseline Project Work Plan for deliverables shall be incorporated in the task order upon acceptance of the project work plan by the Government COR.

4.4.2 Project Reporting

In addition to the Monthly Project Work Plan updates described in Section 4.4.1, the Contractor shall provide monthly status reports to ensure work progress is consistent with and will lead to successful completion of all tasks within work plan according to schedule.

Monthly status reports shall detail progress made during the prior month, progress expected during the next month, resources expended in terms of hours, any significant problems or issues encountered, recommended actions to resolve identified problems, and any variances from the baseline Project Work Plan.

The contractor Task Order Manager for this work effort shall attend the standing monthly Program Manager’s meeting to provide a full status of the project using Microsoft Project to the government FAC-PPM, COR, and Project Sponsors. At the discretion of the FAC-PPM or COR, the contractor may be asked to conduct a monthly status meeting with the government technical leads and key personnel to resolve issued identified/presented at the standing monthly Program Manager’s meeting.

Secure Tool Chain Challenge Problems

4.2 Test Suite

Development

4.3 Challenge Problem

and Test Suite Validation

4.4. Planning and

Reporting

4.1 Challenge Problem

Development

4.1.1 Preliminary

Challenge Problem

Descriptions

4.1.2 Draft Challenge

Problem Documentation

4.1.3 Develop Solutions

for Challenge Problems

5.0 Delivery

All deliverables shall be posted to NIST’s secure shared site or via another secure method (e.g., PGP files via email for proprietary information) as directed by the COR. Deliverables will be evaluated by the COR for completeness, and they will either accept or reject the deliverables within 10 business days of contractor submission. All deliverables shall be provided to the COR.

Task and Deliverable Description Acceptable Quality Standard Media Monitoring Method

Projected Completion Date

4.1.1 – D1 Preliminary Challenge Problem Descriptions (6)

NIST will accept each preliminary challenge problem description based on its clarity, the richness of the security concerns that are realistically represented in the problem description, the appropriateness of the problem’s size relative to the competition’s time constraints, and the configurability via optional requirements. NIST may conditionally accept a preliminary challenge problem with the statement from the contractor that NIST feedback will be incorporated.

MS Word Tech Lead and COR review

To be completed within 4 to 6 weeks after award.

4.1.2 – D2 Draft 6 Challenge Problem Descriptions

In addition to the quality requirements of 4.1.1, the challenge problems shall be documented to a level of detail commensurate with the provided example in Appendix A, so that skilled computer scientists can read them and develop implementations that satisfy them.

MS Word Tech Lead and COR review

To be completed within 4 to 6 weeks after award.

4.1.3 – D3 6 Challenge Problem Implementations

The implementations shall be documented and shall be of high quality suitable for public posting after the competition has been completed. The implementations shall use current best practices for software (e.g., Completed source code and supporting documentation – TAR or ZIP archive.

Tech Lead and COR review

To be completed within 3 to 6 months after award.

Deliverable Description Acceptable Quality Standard Media Monitoring Method

Projected Completion Date modularity, design patterns, the principle of least privilege, use of abstraction, input parameter validation). Documentation shall include explanatory comments for all modules, major functions, and core data structures. The contractor shall employ languages and tools in the implementations that are freely available.

4.2 – D4 6 Test Suites (One per Challenge problem)

NIST will accept each test suite based on whether it operates correctly, covers the functionality of each challenge problem, covers the security requirements of each challenge problem, implements fuzz testing, and produces understandable output. The documentation will be clearly written and detailed enough so that a typical computer scientist will be able to configure and run the test suites. The test suites shall only employ programming languages and tools that are freely available. Documentation of test suite code shall include explanatory comments for all modules, major functions, and core data structures.

Completed source code and supporting documentation – TAR or ZIP archive.

Tech Lead and COR review

Work to be completed within 5 to 9 months after award.

4.3 – D5 Validation exercise implementations

NIST will accept each validation exercise based on whether the test protocol was honored (the correct time given, no advance information on the challenge problem, etc.), on the completeness and clarity of the test documentation, and on the successful scoring of each implementation using the associated test suite.

Completed source code and supporting documentation – TAR or ZIP archive.

Tech Lead and COR review

Work to be completed within 12 months after award.

Deliverable Description Acceptable Quality Standard Media Monitoring Method

Projected Completion Date

4.3 – D6 Validation exercise documentation

NIST will accept each validation exercise based on whether the test protocol was honored (the correct time given, no advance information on the challenge problem, etc.), on the completeness and clarity of the test documentation, and on the successful scoring of each implementation using the associated test suite.

Documentation on how to configure the optional components of the challenge problems to provide an appropriate amount of time pressure for the tests to be very challenging, but not impossible, shall be included.

MS Word Tech Lead and COR review

Work to be completed within 12 months after award.

4.4.1 – D7 Kick-off Meeting artifacts and Project Work Plan

• MS Word / MS Project / MS PowerPoint

• The Kick-off meeting shall be no later than

10 business days after award of the task order

• Electronic copy of the agenda should be delivered to the COR at least 2 business days before the meeting

• The kick-off meeting shall be utilized to introduce all members of the contractor’s team, review all task order requirements and deliverables, review the IPWP, evaluate the contractor’s critical path analysis, and discuss the contractor’s proposed approach

MS Excel/MS Project/email

Tech Lead and COR review

Within 10 business days after task award

4.4.2 – D8 Monthly Status Reports • MS Word / MS Project / MS PowerPoint

• Shall include items accomplished in the previous month, any problems encountered, and solutions implemented, MS Project & Office Tech Lead and COR review

Monthly

Deliverable Description Acceptable Quality Standard Media Monitoring Method

Projected Completion Date planned activities for the next month, and CPI for any labor hours tasks

6.0 Security

All initial work and most of the continuing work shall be performed at the contractor’s facility. Briefings and the all-day validation exercises will be conducted on the NIST campus in Gaithersburg, Maryland.

Contract personnel shall not be required to obtain NIST identification.

7.0 Government-Furnished Property, Material, Equipment, or Information (GFP, GFM, GFE, or GFI)

All work for §4.1, §4.2, and §4.3 of this TO EXCEPT the participation in the mock competition will utilize GFE. To be clear, the computers needed to “compete” in the mock competition should not be GFE. All GFE shall be utilized within the safety and security rules set by NIST.

8.0 Key Personnel

The contractor Key Personnel shall meet the following minimum qualifications for each of the respective required key personnel positions. The titles of the labor categories given below are not mandatory.

They are simply examples of titles suitable to the type of work to be performed by the respective key personnel positions. All contractor key personnel must meet the minimum qualifications associated with the labor category the individuals are proposed/assigned under, as detailed in the IDIQ schedule of labor categories.

a.) Security Engineer 3: This position requires 12 years' experience in technology-oriented security engineering support related to hardware, software, O/S and/or processes. To be clear, this is an operational cybersecurity LCAT.

b.) Developer 3: This position requires a minimum of 7 years of increasingly complex and progressive experience in performing systems analysis, development, and implementation for business, mathematical, engineering, or scientific settings using a variety of information technology resources.

Requires experience with current technologies and, where required for the task, emerging technologies. Must have experience with object or functionally oriented programming languages.

Personnel will be expected to bring creative problem-solving skills to the objectives of the tool chain competition concept.

9.0 Travel

None.

10.0 Place of Performance

All work shall be performed at the contractor’s facility except for briefings and the all-day validation exercises, which shall be performed at the NIST campus in Gaithersburg, Maryland (or virtually depending on campus access restrictions).

11.0 Period of Performance

The period of performance for this task order is 12 months.

Appendix A. Example Man Page of a Challenge Problem

NAME

cardtable – a manager for player and referee processes

SYNOPSIS

[-d path]+ [-a name:key]+ -p path –r path

DESCRIPTION

Cardtable is a server process launched from the command line. The cardtable program implements (simplified) playing card mechanics for client processes that represent various players, and with client processes that represent referees.

The player and referee processes communicate with cardtable via messages exchanged over sockets (format specified below). There may be multiple player and referee processes concurrently.

In response to requests from players and referees, cardtable manipulates decks of cards that it manages, and returns information about cards on the table, including their identities if they are face-up (format specified below), and the status of players' hands.

Cardtable ensures that each player can only observe face-up cards on the table and the cards in that player's hand.

The referee, however, may observe cards on the table whether face-up or face-down, and in any player's hand. Cardtable ensures that players' hands, the decks, and the cards visible on the table are only manipulated according to the rules of play (below).

Cardtable discards any improperly formed input, whether a deck or a message.

OPTIONS

Options are:

-d path Path to a file that specifies a deck. There must be at least one -d option and there could be many. A path may be relative or absolute. If there is not at least one valid deck, cardtable should print "NO DECKS" and exit. The format for a valid deck file is given below.

-a name:key The name of a player that will be allowed to join the table and an integer value that will comprise a shared secret between the player and cardtable, separated by the ‘:’ character. Only a legitimate user on the local system that presents the shared user-specific secret should be allowed to play; others should be ignored.

Only key values that are representable in a 32-bit signed integer should be accepted as valid. Repeated uses of the -a option for the same user should be ignored. If no legitimate player names with well-formed keys are given, cardtable should print "NO PLAYERS" and exit.

-p path The path of a single unix domain socket to which players will connect. Cardtable treats all processes that connect to the player socket as players. If the path cannot be used, cardtable will operate without players (but possibly with referees).

-r path The path of a single unix domain socket to which referees will connect.

Cardtable treats all processes that connect to the referee socket as referees. If the path cannot be used, cardtable will operate without referees (but possibly with players).

MESSAGE FORMAT

Messages are defined using C struct notation. The messages have been designed to be easy to parse rather than to be space-efficient. Request messages arrive on the sockets on which cardtable listens.

Some request messages have corresponding response messages; if a response message is required, cardtable should write it on the same socket connection on which the request messages was received.

The base types used in the struct fields are int_32 (a 32-bit signed integer), and char (an 8-bit ASCII character). String values carried in the character arrays will be either NULL-terminated or exactly the size of the char array fields.

#define BUF_MAX 20

#define SUCCESS 0

#define FAILURE -1

#define JOIN_TABLE_CMD 1

#define LIST_DECKS_CMD 2

#define TAKE_DECK_CMD 3

#define RELEASE_DECK_CMD 4

#define SHUFFLE_DECK_CMD 5

#define START_PLAY_CMD 6

#define START_TURN_CMD 7

#define POP_DECK_CMD 8

#define TAKE_CARD_CMD 9

#define PUT_CARD_CMD 10

#define SHOW_HAND_CMD 11

#define SHOW_TABLE_CMD 12

JOIN_TABLE_CMD:

struct join_table_request_msg { int_32 cmd; /* has value JOIN_TABLE_CMD */ int_32 key; /* shared secret for the requesting user */ char name[BUF_MAX]; /* the name of the user asking to join */

Sent from a process that represents a user (a player or a referee). If the message is received over the socket identified via the –p command line option, the request is on behalf of a player; if the message is received over the socket identified via the –r command line option, the request is on behalf of a referee. For a player request, cardtable should verify that the user name passed in the name field is a legitimate user of the system on which cardtable is running, and should verify that the key field contains a signed integer that matches the key value that was provided for that user via the –a command line option when cardtable was launched. For a referee request, cardtable performs no verification of the key or name fields; cardtable assumes that a referee request is trustworthy because cardtable will be configured so that only trustworthy referee users have access to the referee socket.

Cardtable should discard JOIN_TABLE_CMD messages from players that are not known via the – a option or for players that do not provide the correct shared secret key, or for players that have already joined (based on their names). For a valid message, cardtable should remember whether the process is a player or a referee, should remember the join order of players, and should keep the socket connection with the client process open in order to process further messages from the client. If the request message is not valid, cardtable should close the connection and discard information from the request message.

LIST_DECKS_CMD:

struct list_decks_request_msg { int_32 cmd; /* has value LIST_DECKS_CMD */ struct list_decks_response_msg { int_32 number_of_decks; /* the number of names being returned */ char name[BUF_MAX];

char name[BUF_MAX];

char name[BUF_MAX];

The request message is sent by a process representing a player or a referee over a socket connection that has already been established by the client via a successful JOIN_TABLE_CMD message. Cardtable should return the number of decks and their names in a variable-length response message.

TAKE_DECK_CMD:

struct take_deck_request_msg { int_32 cmd; /* has value TAKE_DECK_CMD */ char name[BUF_MAX]; /* name of the deck to take */ struct take_deck_response_msg { int_32 status; /* SUCCESS or FAILURE */

The request message is sent by a process representing a player over a socket connection that has already been established by the client via a successful JOIN_TABLE_CMD message. If the deck exists and has not already been taken, cardtable should mark the deck as taken, remember which client took it, and return SUCCESS. Otherwise cardtable should return FAILURE.

RELEASE_DECK_CMD:

struct release_deck_request_msg { int_32 cmd; /* has value RELEASE_DECK_CMD */ char name[BUF_MAX]; /* name of the deck to release */ struct release_deck_response_msg { deck exists and the client currently owns it via a prior TAKE_DECK_CMD message, cardtable should mark the deck as free to be taken by any legitimate player, and return SUCCESS.

Otherwise cardtable should return FAILURE.

SHUFFLE_DECK_CMD: (optional) struct shuffle_deck_request_msg { int_32 cmd; /* has value SHUFFLE_DECK_CMD */ char name[BUF_MAX]; /* name of the deck to shuffle */ struct shuffle_deck_response_msg { deck exists and is complete (i.e., no cards have been removed to be placed in players’ hands or on the table top) and the client currently possesses it via a prior TAKE_DECK_CMD message, cardtable should randomize the order of the cards in the deck, and return SUCCESS. Otherwise, cardtable should return failure.

START_PLAY_CMD:

struct start_play_request_msg { int_32 cmd; /* has value START_PLAY_CMD */ char name[BUF_MAX]; /* name of the player to start the play */ struct start_play_response_msg {

The request message is sent by a process representing a referee over a socket connection that request was sent by a referee, and if the indicated player exists, cardtable assigns that player to be the current player and returns SUCCESS. Otherwise, cardtable returns FAILURE.

START_TURN_CMD

struct start_turn_request_msg { int_32 cmd; /* has value START_TURN_CMD */ struct start_turn_response_msg { requesting player is the next player as determined by the order in which players joined the cardtable (with the last followed by the first), and there is no operation currently in progress (such as shuffle), cardtable assigns the requesting player to be the current player and returns SUCCESS. If cardtable is currently busy when the request arrives, it waits for the current work to complete before processing the request message.

POP_DECK_CMD

struct pop_deck_request_msg { int_32 cmd; /* has value POP_DECK_CMD */ char name[BUF_MAX]; /* name of the deck to pop */ int_32 face_up_or_down; /* has value 0 for up, 1 for down */ int_32 destination; /* 0 for table, or which player */ struct pop_deck_response_msg { identified deck exists, and if the requesting player currently has it taken, and the destination and face_up_or_down fields have valid values, and the deck is not empty (it could be empty if all it cards have already been distributed), cardtable moves one card from the top of the deck to the destination indicated in the request, with visibility set based on the face_up_or_down field, and returns SUCCESS. Otherwise, cardtable returns FAILURE. The destination field encodes where the card should be moved as follows: 0 means place the card on the center of the table (forming a stack); any other integer value refers to a player by the order in which the players joined the cardtable (starting with 1).

TAKE_CARD_CMD (optional) struct take_card_request_msg { int_32 cmd; /* has value TAKE_CARD_CMD */ int_32 source; /* 0 for the table; or 1 for the deck */ char name[BUF_MAX]; /* name of the deck to take from */ struct take_card_response_msg { char card[BUF_MAX]; /* identity of card taken, */ has already been established by the client via a successful JOIN_TABLE_CMD message. The request names the source from which the card should be taken. If the source field is 0, the card is taken from the top of the cards in the center of the table, if any cards are available. If the source field is 1, the card is taken from the named deck, if it exists and is not owned by another player, and is not empty. If a card can be taken, cardtable returns SUCCESS and the identity of the taken card, formatted in the card return field according to the “card:” rule in the deck file format documented below (i.e., a card-type followed by a suite, separated by white space), and NULL-terminated. If a card cannot be taken because the deck is invalid, because the source is empty, or because the source is a deck and another player currently owns it, cardtable returns

FAILURE.

PUT_CARD_CMD (optional) struct put_card_request_msg { int_32 cmd; /* has value PUT_CARD_CMD */ char card[BUF_MAX]; /* name of card to put */ int_32 destination; /* 0 for table, or 1 for the deck */ int_32 face_up_or_down; /* has value 0 for up, 1 for down */ char name[BUF_MAX]; /* name of the deck to put to */ struct put_card_response_msg { has already been established by the client via a successful JOIN_TABLE_CMD message. The card field should be a string formatted according to the “card:” rule in the deck file format (i.e., a card-type followed by a suite, separated by white space); the destination field indicates whether the card should be placed on the table or in the deck identified by the name field. The face_up_or_down field indicates the visibility status of the card after it has been put. If the cmd is PUT_CARD_CMD, card is properly formatted and is a card that the requesting player currently holds, the destination field is either 0 or 1, the face_up_or_down field is either 0 or 1, and (assuming the destination field is 1) the name field contains a valid deck, cardtable should add the designated card to the designated destination (on top) with the visibility set as specified, remove the card from the requesting player’s hand, and return SUCCESS. Otherwise, cardtable should make no changes and return FAILURE.

SHOW_HAND_CMD

struct show_hand_request_msg { int_32 cmd; /* has value SHOW_HAND_CMD */ struct show_hand_response_msg { int_32 number_of_cards; /* the number of cards being returned */ char name[BUF_MAX]; /* name of a card */ char name[BUF_MAX]; /* name of a card */ char name[BUF_MAX]; /* name of a card */ has already been established by the client via a successful JOIN_TABLE_CMD message. Cardtable should return the number of cards in the requestor’s hand and their names in the variable-length response message. Each card should be formatted according to the “card:” rule in the deck file format described below (i.e., a card-type followed by a suite, separated by white space). If the request message cmd field has the value SHOW_HAND_CMD, and the requestor is a player (rather than a referee), cardtable should fill in the return fields and return SUCCESS;

otherwise CARDTABLE should set the status field to FAILURE and the number_of_cards field to 0.

SHOW_TABLE_CMD (optional) struct show_table_request_msg { int_32 cmd; /* has value SHOW_TABLE_CMD */ struct show_table_response_msg { int_32 number_at_center; /* cards in the center of the table */ char name[BUF_MAX]; /* name of a card */ char name[BUF_MAX]; /* name of a card */ int_32 number_of_hands; /* number of hands being returned */ int_32 number_of_cards; /* number of cards for first hand */ char name[BUF_MAX]; /* name of a card */ char name[BUF_MAX]; /* name of a card */ int_32 number_of_cards; /* number of cards for second hand */ char name[BUF_MAX]; /* name of a card */ char name[BUF_MAX]; /* name of a card */ char name[BUF_MAX]; /* name of a card */ int_32 number_of_cards; /* number of cards for last hand */ char name[BUF_MAX]; /* name of a card */ char name[BUF_MAX]; /* name of a card */

The request message is sent by a process representing a player or referee over a socket connection that has already been established by the client via a successful JOIN_TABLE_CMD message. Cardtable should return information on the cards in the center of the table, and on the cards held by each current player, in the variable-length response message structure. Cardtable should set number_at_center to be the number of cards currently in the center of the table.

Cardtable should set number_of_hands to be the current number of players. For each player, cardtable should return card information, as with the SHOW_HAND_CMD response message, except that, when the requestor is a normal player, the face-down cards in other players’ hands or in the center of the table should be given the value “face-down” in the name fields. If the requestor is a referee, the identities of all cards should be returned formatted as in the SHOW_HAND_CMD response message.

DECK FILE FORMAT

(optional: a simpler, fixed format)

(optional: guarantee the program that a deck is always well-formed)

The program will read card decks from a configuration file given on the command line, formatted as given in the grammar below. White space (tabs, newlines, spaces) may appear before or after the elements of the grammar and should be ignored. In the grammar below, NAME is a string value comprised of characters that match the regular expression [A-Za-z0-9_]+ and that specify a proper noun (like "fred") associated with the deck. The cards read from the file may not constitute a correct deck.

Some cards may be missing or repeated. Cards may specify nonexistent suites or card-types (see grammar), and may not follow the format. An invalid deck should be ignored.

A valid deck has one of each "card-type" for each "suite" (see below).

For a valid deck, the order of the cards should preserved for subsequent operations. The first card in a deck file corresponds to the top of the deck.

deck: 'deck' NAME '{' card-list '}' card-list: card-list ',' card

| card card: card-type suit suit: 'spades' | 'diamonds' | 'clubs' | 'hearts' card-type: 'ace' | 'king' | 'queen' | 'jack' | '10' | '9' | '8' | '7' | '6'

| '5' | '4' | '3' | '2'

SECURITY POLICY

1) Commands are served only for authorized players and referees as determined by the –a option for players and the socket files (for referees).

2) A referee is defined as a client that is communicating on one of the referee sockets; some requests from referees (e.g., show_table) should return extra information.

3) Players do not play out of turn.

4) The join-order of players is used for ordering turns.

5) Only a referee can initiate play.

6) Only a player can take a turn.

7) An invalid deck will not be used.

8) A deck can only be owned by only one player at a time.

9) Players cannot modify each others’ hands except when dealing, when the dealer can add cards to other players' hands.

10) Any player can view the table at any time, but not the values of cards that are face down.

11) A player can only view face-up cards in the hands of other players.

12) A referee can view all cards of all players.

13) A referee cannot take a deck, modify a deck or modify a player’s hand.

14) The cards in a shuffled deck have (pseudo) random order.

ASSURANCES Provided to Cardtable

1) The files given to cardtable will not be deleted, moved, or modified while cardtable is running.

2) Socket connections are not tampered.

3) The request messages will be structured as given in the protocol specification; i.e., there will be no partial or inconsistent messages.

EXIT STATUS

Cardtable should exit with 0 on success, and 1 on failure.

IMPLEMENTATION HINTS

If a player or referee process exits, this will be an event that causes the select() system call to return in cardtable even though there are no bytes to read; the old socket needs to be discarded.

The following two C code snippits are offered to help participants move quickly through socket programming details.

An Example of a Socket-based Client (no error or security checking)

#include <stdio.h>

#include <sys/socket.h>

#include <sys/un.h>

#include <string.h>

#include <unistd.h> int main(int argc, char *argv[]) struct sockaddr_un sun;

sun.sun_family = AF_UNIX;

strcpy(sun.sun_path, "psock");

sun.sun_len = SUN_LEN(&sun);

int sock = socket(PF_UNIX, SOCK_STREAM, 0);

int ret = connect(sock, (struct sockaddr*)&sun, sun.sun_len);

char msg[BUF_MAX];

strcpy(msg, "a message");

int w_bytes = write(sock, (void*)&msg, sizeof(msg));

An Example of a Corresponding Socket-based Server (no error or security checking)

#include <stdio.h>

#include <sys/stat.h>

#include <unistd.h>

#include <sys/socket.h>

#include <sys/un.h>

#include <string.h>

#include <stdlib.h> void serve_clients(char *player_path, char *referee_path) struct stat statb;

/* Clean up old socket files if they exist. */ int ret = stat(player_path, &statb);

if (statb.st_mode & S_IFSOCK) { unlink(player_path);

ret = stat(referee_path, &statb);

if (statb.st_mode & S_IFSOCK) { unlink(referee_path);

/* create player socket and listen on it */ struct sockaddr_un…