Email Gateway (Aug 22 2022 at 10:12): Email Gateway (Aug 22 2022 at 10:12):From: Gerwin Klein <Gerwin.Klein@nicta.com.au>
Three new AFP entries by Pasquale Noce are available from http://afp.sf.net :
Reasoning about Lists via List Interleaving
http://afp.sourceforge.net/entries/List_Interleaving.shtml
Abstract:
Among the various mathematical tools introduced in his outstanding work on
Communicating Sequential Processes, Hoare has defined "interleaves" as the
predicate satisfied by any three lists such that the first list may be split
into sublists alternately extracted from the other two ones, whatever is the
criterion for extracting an item from either one list or the other in each step.
This paper enriches Hoare's definition by identifying such criterion with the
truth value of a predicate taking as inputs the head and the tail of the first
list. This enhanced "interleaves" predicate turns out to permit the proof of
equalities between lists without the need of an induction. Some rules that allow
to infer "interleaves" statements without induction, particularly applying to
the addition or removal of a prefix to the input lists, are also proven.
Finally, a stronger version of the predicate, named "Interleaves", is shown to
fulfil further rules applying to the addition or removal of a suffix to the
input lists.
The Ipurge Unwinding Theorem for CSP Noninterference Security
http://afp.sourceforge.net/entries/Noninterference_Ipurge_Unwinding.shtml
Abstract:
The definition of noninterference security for Communicating Sequential
Processes requires to consider any possible future, i.e. any indefinitely long
sequence of subsequent events and any indefinitely large set of refused events
associated to that sequence, for each process trace. In order to render the
verification of the security of a process more straightforward, there is a need
of some sufficient condition for security such that just individual accepted and
refused events, rather than unbounded sequences and sets of events, have to be
considered.
Of course, if such a sufficient condition were necessary as well, it would be
even more valuable, since it would permit to prove not only that a process is
secure by verifying that the condition holds, but also that a process is not
secure by verifying that the condition fails to hold.
This paper provides a necessary and sufficient condition for CSP noninterference
security, which indeed requires to just consider individual accepted and refused
events and applies to the general case of a possibly intransitive policy. This
condition follows Rushby's output consistency for deterministic state machines
with outputs, and has to be satisfied by a specific function mapping security
domains into equivalence relations over process traces. The definition of this
function makes use of an intransitive purge function following Rushby's one;
hence the name given to the condition, Ipurge Unwinding Theorem.
Furthermore, in accordance with Hoare's formal definition of deterministic
processes, it is shown that a process is deterministic just in case it is a
trace set process, i.e. it may be identified by means of a trace set alone,
matching the set of its traces, in place of a failures-divergences pair. Then,
variants of the Ipurge Unwinding Theorem are proven for deterministic processes
and trace set processes.
The Generic Unwinding Theorem for CSP Noninterference Security
http://afp.sourceforge.net/entries/Noninterference_Generic_Unwinding.shtml
Abstract:
The classical definition of noninterference security for a deterministic state
machine with outputs requires to consider the outputs produced by machine
actions after any trace, i.e. any indefinitely long sequence of actions, of the
machine. In order to render the verification of the security of such a machine
more straightforward, there is a need of some sufficient condition for security
such that just individual actions, rather than unbounded sequences of actions,
have to be considered.
By extending previous results applying to transitive noninterference policies,
Rushby has proven an unwinding theorem that provides a sufficient condition of
this kind in the general case of a possibly intransitive policy. This condition
has to be satisfied by a generic function mapping security domains into
equivalence relations over machine states.
An analogous problem arises for CSP noninterference security, whose definition
requires to consider any possible future, i.e. any indefinitely long sequence of
subsequent events and any indefinitely large set of refused events associated to
that sequence, for each process trace.
This paper provides a sufficient condition for CSP noninterference security,
which indeed requires to just consider individual accepted and refused events
and applies to the general case of a possibly intransitive policy. This
condition follows Rushby's one for classical noninterference security, and has
to be satisfied by a generic function mapping security domains into equivalence
relations over process traces; hence its name, Generic Unwinding Theorem.
Variants of this theorem applying to deterministic processes and trace set
processes are also proven. Finally, the sufficient condition for security
expressed by the theorem is shown not to be a necessary condition as well, viz.
there exists a secure process such that no domain-relation map satisfying the
condition exists.
Enjoy!
Gerwin
The information in this e-mail may be confidential and subject to legal professional privilege and/or copyright. National ICT Australia Limited accepts no liability for any damage caused by this email or its attachments.
Last updated: Apr 27 2024 at 01:05 UTC