Security Policy for SCG

The Specker Challenge Game = The Scientific Community Game

Acceptance of false data is a big issue for SCG, but one which can be solved through careful organization. The communication language is defined by two grammars: PlayerTrans (agent -> admin) and PlayerContext (admin -> agent). The grammars define the syntax rules but we also need semantic rules to check the legality of the data.

Semantic checks for PlayerTrans

The price of a challenge is in [0..1].

A problem instance must be legal: set of declared variables must be a super set of the set of used variables. a clause must contain 3 distict variables. the weight of a clause is a positive integer > 0. the problem type must be a set of distinct integers. the relation number must be between 0 and 255. the number of clauses must be at least 1.

The number of clauses and the number of variables is bounded by the maximum number of allowed clauses.

Problem instance in a provide transaction must conform to the corresponding problem type. I.e., it only uses relations mentioned in the type.

A solution of a solved challenge must be a solution to the instance that was provided. A solution to a MAXCSP problem must assign enough variables so that each clause is either satisfied or unsatisfied.

A provided problem must satisfy the predicate of the challenge.

The challengee must be a player in the game.

An agent is not allowed to accept its own challenges.

More MAXCSP specific checks: For TBall, Problem type must be a singleton set. For Slow Pitch Softball, relations must form an implication tree.

Semantic checks for PlayerContext

This information comes from the admin and is assumed to be legal.

SCG Rules

They are in the requirements document section 5.3. These rules are intended to make the virtual scientists = agents productive members of their community. SCG(X) produces knowledge about domain X. The undiscounted challenges make up this knowledge base. Although not a part of security, it is important to know the reason for the rules:

The virtual scientists are encouraged to 
  offer results that are not easily improved.
  offer results that they can successfully support.
  quote related work and show how it improves on previous work (reoffer).
  prove results if the current state of the art allows.
  publish results of an experimental nature with 
    an appropriate confidence level.
  be well-rounded: solve posed problems and 
    pose difficult problems for others (Like the Four Color Conjecture).
  never cheat
  stay active but not hyperactive
  become famous (scientist with highest reputation wins)
  have the best practical algorithms for the given domain

This replaces rule 2 in 5.3: Ensuring activity but avoiding hyperactivity

NumProposals = numOffers + numReoffers;
NumOppositions = numAccepts + numReoffers;

config.getMinProposals() <= NumProposals <= config.getMaxProposals();
config.getMinOppositions() <= NumOppositions

This can be summarized as: They must propose and oppose. A reoffer counts as both. All the other rules in 5.3 apply.

The SCG Security Policy

All agents are responsible for only delivering PlayerTrans sentences that are legal.

The administrator is defined by the code in the isLegal(PlayerTrans trans). http://www.ccs.neu.edu/home/lieber/courses/cs4500/f09/files/source/SCGLibs/scg/scg-game.beh

If the administrator does not break the game, she is by definition correct.

If isLegal needs to check more rules you send to the class a message containing a PlayerTrans and PlayerContext and you motivate the additional check that needs to be done. This counts as significant class participation.

On Tuesday nights, to debug the administrator, attacks on the integrity of the game are allowed. Trying to violate rules is encouraged. But don't violate any college rules or violate a law.

The teams are encouraged to detect integrity violations. If a team found a vulnerability they need to report it to the class soon after the competition. The administrator will be improved based on this input. This counts as significant class participation.

The agents' developers are responsible for running their agent on a secure computer preventing many disclosure and usurpation threads. The information sent between administrator and agents should be encrypted. This is currently missing but might be added later.

Gentleman agreement added on Nov. 20: The purpose of our game is to accumulate knowledge about MAX-CSP and to develop good algorithms for solving MAX-CSP. Therefore, we make the following gentleman agreement: Tactical approaches to winning the game are discouraged. A strategic approach to your agent is encouraged that uses good algorithms for solving MAX-CSP problems with many variables and constraints.

Our security policy evolves over time.

(1) ALL TBall
(2) ALL and SECRET TBall.
(3) ALL and SECRET SLOW PITCH SOFTBALL. At least 20% of the offered challenges must be of the second kind.
(4) ALL FAST PITCH SOFTBALL level 2 reduced. 
(4new) ALL FAST PITCH SOFTBALL.
(5) ALL and SECRET FAST PITCH SOFTBALL. At least 20% of the offered challenges must be of the second kind.

Notes: challenges(1) subset challenges(2). challenges(2) subset challenges(3). challenges(4) subset challenges(5).

(1) at the beginning of the course. (2) Oct. 15, 19, 22. (3) starts Oct. 26.

Karl Lieberherr, Ahmed Abdelmeged, Bryan Chadwick, Alex Dubreuil