Draft 3
20040907
mcl

The GOSSiP architecture

The fundamental unit of the GOSSiP architecture is the GOSSiP node.  A
GOSSiP node:

 * stores information about email sender identities
 * stores information about other GOSSiP nodes
 * adjusts this information according to direct experience and feedback
 * provides a reputation score when supplied with an identity
 * provides a confidence rating for each reputation score computed
 * accepts feedback on messages recently submitted by an identity



A GOSSiP node deployment connects the GOSSiP node to three types of
entities:

 * one or more Mail Transport Agents (MTAs)
 * zero or more other GOSSiP nodes (peers)
 * one or more feedback mechanisms



A GOSSiP node accepts three forms of input:

 * a query from an MTA or peer
 * a query response from a peer
 * feedback from a feedback mechanism

Structure of a GOSSiP Query
 A GOSSiP query consists of four parts:
   1) A tag identifying the input as a query 
   2)  The identity queried
   3)  A Time-To-Live (TTL) value
   4)  An Unique Message-Identification String (UMIS)



Identities
 Queried identities consist of two parts:
   1) The right-hand-side (RHS) of the RFC2821 MAIL FROM: address
      supplied by the sender (i.e., all characters to the right of
      the "@" symbol)
   2) The IP address of the sender, as determined by the mail server
      when the sender connects, or some tag as determined by the
      MTA agent, e.g., indicating that the address has passed an
      authentication test.



TTLs
 The TTL of a query constrains the depth to which a query will be 
propagated in the GOSSiP network.  When a mailserver initiates a query, 
the TTL is set according to a value specified by the administrator at 
deployment time.  The TTL will be decremented as the query is propagated
through the network of peers.  When the TTL reaches 0, the propagation
will stop.



Unique Message-Identiffication String (UMIS)
 The UMIS of a query is a unique string generated by the GOSSiP MTA
agent and inserted into an incoming message as a GOSSiP-ID: header 
prior to spooling, if the MTA agent instructs the MTA to continue
processing the message based on the response from the GOSSiP node.




How Queries Are Received
  A GOSSiP node receives a query on a predetermined high-numbered port 
via TCP.  When a connection is attempted, the GOSSiP node compares the
source IP to a list of peers and MTAs.  If the source IP matches one of
the addresses on that list, the connection is allowed to proceed.  
Otherwise, the connection is reset.  The connection between the MTA
agent and the GOSSiP node may or may not be encrypted via SSL.  The
connections among peers are always SSL-encrypted.



How Queries Are Processed
  Once a query connection has been accepted, the GOSSiP node accepts
and parses the query.  The connection is held open until
the node supplies a response to the sender.  The GOSSiP node checks
the TTL value.  If the TTL is equal to 0, the GOSSiP node responds 
with the reputation information and confidence value for that 
identity.  Otherwise, the GOSSiP node decrements the TTL by 1 and
passes along the query to each of its peers.  The GOSSiP node waits
for a response from each of its peers, or until a timeout occurs,
whichever comes first.  Once one of these two conditions have been
satisfied, the GOSSiP node computes a reputation score and confidence
value for the queried identity and responds to the original sender
with this information.  The original sender should acknowledge receipt
of this information and close the TCP connection.  If the original
sender does not receive a response before a timeout occurs, the
original sender may close the connection.



Reputation Score
 Reputation is defined as a value indicative of an entity's behavior
over time, as evaluated by one or more GOSSiP nodes.

A GOSSiP node tracks reputation for:
 * sender identities
 * peers

The reputation score is represented by the function:
                              ((P(h) - P(s))k)
                             e
Reputation(i) = 200 * ( ------------------------- - 0.5 )
                              ((P(h) - P(s))k)
                         1 + e

Which is essentially the Rasch logistic model.  
P(h) is the ratio of ham accounted for within N to the size of N.
P(s) is the ratio of spam accounted for within N to the size of N.
k is a constant which effectively adjusts the sensitivity of the 
  reputation model to small changes in P(h)-P(s).  Recommended
  values for k are in the range of 2-10.  As k->0, Reputation(i)
  becomes more linear.
i is a given identity.



The Reputation Cache
 The GOSSiP node contains a FIFO cache of the last N local queries.
Each entry in this cache is either 0 or 1, with 0 indicating spam and 1 
indicating nonspam (a.k.a. "ham").  The value for N is set at deployment 
time, and should be sufficiently large to ensure a representative sample 
of data.

The values in this reputation cache are obtained through the feedback
mechanism.

When an entry is made in the reputation cache, the seconds since epoch
at the time of entry is recorded.  This value is a single variable, and
is updated every time a reputation cache entry is made.  Each reputation
cache has such a "time last seen" variable associated with it.  This
value is used in the computation of the confidence value for a
reputation score.



Confidence Value
 The confidence score is represented by the function:

Confidence(R(i)) = [ sum(o) / N ] * age

R(i) is the reputation score for a given identity i.
sum(o) is the total number of observations stored in the reputation cache.
N is the size of the reputation cache.

age is represented by the following function:
                 age(o)
age = 100 * (  ---------- )
                 age(n)

age(n) = seconds since epoch at time of computation.
age(o) = seconds since epoch at time of last local transaction with identity.

This ensures that the confidence value reflects not only the amount
of data the node has for a given identity, but how old that data is.


How Reputation is Computed
  When one of two conditions have been met:
    1) The GOSSiP node has received a query with a TTL of 0
    2) Zero or more of the GOSSiP node's peers have timed out while the
       node was waiting for a query response from them, and the remaining
       peers have supplied a query response

the GOSSiP node checks its cache of recently-seen UMISes.  If the UMIS
in the query is not one the node has recently seen, it will compute a
reputation score and confidence value for the identity, and respond to
the source of the query with this data.


The computation of reputation proceeds as follows:
  1) The node computes a reputation score based on its own data
  2) The node computes a confidence value based on its own data
  3) The node adjusts reported reputation scores according to the
     associated confidence values
  4) The node adjusts these adjusted reputation scores according to
     the reporting peer's reputation
  5) The node aggregates its own reputation and confidence scores with
     those received from its peers
  6) The node returns these aggregate scores to the original source of
     the query

The reputation score in step 1 is computed according to the formula in 
the section titled, "Reputation Score".  At this time, peer
reputations are also updated (see the section titled, "Peer Reputation"
for details).

The confidence value in step 2 is computed according to the formula in
the section titled, "Confidence Value".

Once the node's own reputation score and confidence value have been
computed, the node adjusts all reputation scores by their associated
confidence values.  The confidence value is in the range [0..100], and
may be considered a percentage.  Thus, the confidence adjustment for
a reputation score R(i) for a given identity i is:

                C(R(i)
aR(i) = R(i) * --------
                 100

The node adjusts these new reputation scores according to how much
the node trusts each peer (R(p)):

If R(p) >= 0, aR(i) is unchanged.
If R(p) < 0, aR(i) is decreased according to the following formula:

                       R(p)
TR(i) = aR(i) * abs( -------- )
                       100

The node then computes the mean of all adjusted reputation scores for
the current query (i.e., the mean of each reputation response from its
peers and its own reputation score), and the standard deviation of
each reputation score.  Any reputation score whose standard deviation
is greater than 3 is eliminated, and the mean of the remaining reputation
scores is computed.

The mean of the confidence scores associated with the remaining reputation
scores is also computed.

The node returns the averaged reputation score and the averaged confidence
value to the original source of the query.




Peer Reputation
 Each GOSSiP node computes the reputation of its peers, and uses this
information to modulate responses received from each peer.  The node
keeps a FIFO cache of size M of interactions with each peer.  The
values stored in this cache are -1, 0, or 1.  0 indicates no data.
1 indicates a query response with which the node agreed.  -1 indicates
a query response with which the node disagreed.  The peer reputation
score is computed exactly as described in the section entitled, "Reputation
Score".  M is significantly smaller than the size of identity reputation
caches, however.  A value of 100 is reasonable, though a smaller value
would certainly work as well.

Agreement is determined at the time a node computes its own reputation
score, prior to score aggregation and reporting.

As with the reputation cache, the peer reputation cache is hashed such that
each value is indexed by the UMIS to which it refers.

The effect of peer reputation is meant to mediate the input of those peers
that have repeatedly demonstrated an opinion that differs with that of the
node itself. 



Feedback Mechanism
 A GOSSiP node may receive feedback on a high-numbered TCP port.
The feedback is composed of two items:
  1) The UMIS associated with a specific message, and an integer
value indicating that the message was evaluated as spam (0) or ham (1).

The GOSSiP node will accept this information and close the connection with 
the feedback mechanism.  The UMIS will be compared with a FIFO cache of size
P of recently seen UMIS strings, where P is sufficiently large to reflect
the previous Y minutes of traffic, providing a limited window in which
feedback may be submitted for a given message.  If the UMIS is found in
this cache, it is removed from the cache, and the evaluation is added to
the identity's data.



Relay-Only Nodes
 The GOSSiP architecture allows for the deployment of "relay-only" nodes --
nodes that would not track any data of their own, but act instead as
agents that pass along queries among a set of disparate nodes.  By
using a wildcard in the Replied-To cache, the comparison will always
succeed, forcing the node to exclude itself from participating in any
reputation/confidence computation.

 The reason for wanting such relay-only nodes lay in the "small world"
phenomenon, which relies on both strong and weak social associations.
GOSSiP's immediate peer structure provides adequate stong association
linkage, but the architecture lacks a good weak association mechanism.
By deploying relay-only nodes that join otherwise disparate clusters
of peers, the necessary weak associations are introduced.