Version 1.1 of acs/ac-00247.txt

Unformatted version of acs/ac-00247.txt version 1.1
Other versions for file acs/ac-00247.txt

!standard A.18.4(75.1/3)          13-05-09 AC95-00247/00
!class confirmation 13-05-09
!status received no action 13-05-09
!status received 13-02-08
!subject Question about extent of tampering checks for formal subprograms
!summary
!appendix

From: Matthew Heaney
Sent: Friday, February  8, 2013  12:46 AM

I'm making some changes to GNAT, associated with AI05-0022, available here:

http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai05s/ai05-0022-1.txt

I have a question about how extensive are the tampering checks.
Specially, the ordered map packages provide operators to compare cursors and
keys.  These are operations do not manipulate map containers, only cursors (and
keys).

My question is, is a tampering check required for these operators too?

In practice, to satisfy other sorts of checks, type Cursor must be implemented
with a pointer to its associated container.  So in principle, the relational
operator (to compare a pair of cursors, say) could change the state of the
associated container (in order to detect tampering), before actually calling the
generic formal "<" operator, and then revert the container state immediately
following the comparison. This would prevent mischief to the associated
container while the cursor comparison executes.

But was such a tampering check intended by this AI, to also include the case of
the cursor and key comparison operators?

***************************************************************

From: Randy Brukardt
Sent: Friday, February  8, 2013  1:35 AM

> I'm making some changes to GNAT, associated with AI05-0022, available
> here:
>
> http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai05s/ai05-0022-1.txt
>
> I have a question about how extensive are the tampering checks.
> Specially, the ordered map packages provide operators to compare
> cursors and keys.  These are operations do not manipulate map
> containers, only cursors (and keys).
>
> My question is, is a tampering check required for these operators too?

No, but see below.

> In practice, to satisfy other sorts of checks, type Cursor must be
> implemented with a pointer to its associated container.  So in
> principle, the relational operator (to compare a pair of cursors, say)
> could change the state of the associated container (in order to detect
> tampering), before actually calling the generic formal "<" operator,
> and then revert the container state immediately following the
> comparison.
> This would prevent mischief to the associated container while the
> cursor comparison executes.
>
> But was such a tampering check intended by this AI, to also include
> the case of the cursor and key comparison operators?

The AI defines tampering in a formal subprogram to be a Bounded Error. It does
*not* mandate a tampering check; rather, it mandates that the operation either
work properly or raise Program_Error. The intent is to say that an
implementation that walks a dangling pointer (because of tampering) is incorrect
(that is, erroneousness is not allowed). For an operation like Find, it's
probably necessary to make a tampering check, because otherwise the iteration
implied by the operation could walk into space.

But for an operation like "<", there is no need to "dereference" a cursor after
the call to the generic formal parameter function, so nothing bad could happen
if tampering is undetected. And the operation can safely return a result without
a problem even if an element is deleted from the container.

Thus, if the operation does not use any cursors after the call to a formal
function, it probably does not need a tampering check. OTOH, if the operation
does use a cursor (or rather the embedded pointer), then it either needs a
tampering check or some other check to prevent trouble. (In the case of a
vector, it might be possible to do a length check instead, just to ensure that
the cursor points at an in-use element.)

The point is that no container operation can cause erroneous execution for this
reason; the results might be garbage if the formal function is screwy enough,
but the operation should either return a result or raise an exception. Doing
other things is not allowed (like writing some other container's memory).

Hope this helps.

***************************************************************

From: Matthew Heaney
Sent: Wednesday, March 20, 2013  12:17 AM

> The AI defines tampering in a formal subprogram to be a Bounded Error.
> It does *not* mandate a tampering check; rather, it mandates that the
> operation either work properly or raise Program_Error. The intent is
> to say that an implementation that walks a dangling pointer (because
> of tampering) is incorrect (that is, erroneousness is not allowed).
> For an operation like Find, it's probably necessary to make a
> tampering check, because otherwise the iteration implied by the operation could walk into space.

An issue came up about what should happen when the container object is declared
as a constant.  For example, suppose we try to find something in an empty
container, e.g. the one declared as a constant in the container packages:

package List_Types is
   new Ada.Containers.Doubly_Linked_Lists (Integer);

declare
   C : Cursor := List_Types.Empty_List.Find (42); begin
   null;
end;

In the general case, implementing a tampering check requires changing some
physical state.  What are the consequences of changing the state of a container
object declared as a constant?  (In the example above, List_Types.Empty_List.)

Of course, we can handle an empty container as a special case, to prevent having
to manipulate any state.  But that only defers the problem, since we can say:

declare
   L : List_Types.List;
begin
   L.Append (42);
   declare
     L2 : constant List_Types.List := L;
     C2 : Cursor := L2.Find (42);
   begin
     null;
   end;
end;

Any thoughts?

***************************************************************

From: Randy Brukardt
Sent: Wednesday, March 20, 2013  2:56 PM

> An issue came up about what should happen when the container object is
> declared as a constant
...
> In the general case, implementing a tampering check requires changing
> some physical state.  What are the consequences of changing the state
> of a container object declared as a constant?  (In the example above,
> List_Types.Empty_List.)

This is a complicated question for which I conclude that there is no significant
problem. But it will take a while to get there, so bear with me. (Or skip to the
bottom if you're not Matt. :-)

First, as I noted previously, the only true requirement is to avoid erroneous
behavior. If the implementer can find another way to do that, that may very well
be preferred to using a tampering check (as that is relatively expensive; OTOH,
it's a sunk cost because routines involved have to be able to handle that for
other kinds of tampering so there is little incremental cost).

Second, "constant" does not necessarily mean *constant* (unchangable). There are
a number of reasons for that. The obvious one is that "constant" only applies to
the top level of a private object; it does not (necessarily) apply to data
accessed via an indirection. (See, for instance, the fact that a random number
"generator" is technically a constant, yet it has to change every time Random is
called).

Moreover, even the top-level data can be modified if the language provides a
mechanism to get a writable access to it. For controlled objects, the
Initialize/Adjust/Finalize routines provide writable access to a constant;
similarly, for immutably limited types, the current instance provides such
access. Thus, these kinds of types are never really constant, regardless of how
they're declared. See 3.3(13/3) for the formal definition, and AI05-0054-2 for a
lot more on this topic.

Because of these rules, there is no issue whatsoever for any of the unbounded
forms, which will have to contain a controlled object somewhere and merely have
to put the tampering code there to work for constants.

The bounded forms, unfortunately, are a different kettle of fish, as making them
controlled is prohibited. (This is overspecification, IMHO, since an
implementation of finalization like GNAT's would be sufficient to allow proper
static analysis of any controlled parts to allow use in safety-critical
programs. But let's ignore that.)

Here, there is little practical problem with modifying the objects. A bounded
container object is tagged, meaning that they have to be passed by-reference.
Thus, 'Access (and 'Unchecked_Access) is allowed, and at worst, one can use an
Unchecked_Conversion to a writable access to get the ability to change the
tampering check data.

Such code is formally erroneous, which is not allowed in the container
implementation. That means that the compiler will need some mechanism (like an
aspect) to tell itself not to use any "constantness" information in
optimizations. (For some compilers, that would not be necessary, as there aren't
any optimizations depending on that information -- and even if there is, it's
unlikely to be triggered in the container case, so it probably is enough
initially to assume that there is no problem. But I'd err on the side of caution
here.) All such an aspect would mean is that constant objects of the type should
be treated similarly to constant controlled objects for optimization/erroneous
execution purposes (it wouldn't be a new property so much as a new way to assign
an existing property). It would actually make sense to standardize such a thing
(that would allow static analysis tools to know about it), but it's too late for
Ada 2012 so a language-level fix will have to wait a while.

It of course would have been better if the parameter mode of operations that
might involve tampering were "in out", but it's clearly too late for that. (And
its not possible for "=" in any case.) And remember that the oddity only applies
to the bounded forms (the unbounded forms have no issue here), so most programs
would not run into any issue.

Let's now look at the problem from the other side. Does allowing tampering
checks on constant container objects cause any usability problems?

The first part of the answer is to note that the tampering checks are almost
always associated with the call of the single subprogram (and the case we're
currently worrying about, Find, is one such case). The checks are turned on AND
off by that single call, so the only way to notice the change in state is to
make another call during the course of the initial call. The only exception I
know of is the Iterator object returned by the Iterate functions, but this
object acts similarly to the "single call".

How could we get another call? One way is for another task to make a call.
However, such a call would violate the requirement A(3) [this is a paragraph 3
in the introduction to Annex A, a bad place to put a normative rule, but that's
where it is]. (Note that this wording is strengthened by new wording in
AI12-0052-1, to include all concurrent calls of language-defined subprograms.)
That means that there is no requirement that two concurrent calls with the same
object from different tasks work as described in the Standard. So programmers
should not be depending on such calls without using some technique to ensure
that they are not concurrent -- and in that case, no tampering change would be
visible. (I'm not sure that this rule applies to the iterator object - it's hard
to argue that its overlapping with its associated container, but it should.
Perhaps we'll need another AI to fix that.)

The only other way to get another call is for some call-out from the original
routine (Find in this case) to make a call into the library. And of course, this
is the case we're trying to detect. So it's obviously not a problem to have a
state change for calls from the same task.

From all of this, I conclude that it is OK to modify constants in the case of
needed tampering checks.

Note that as a practical matter, you can avoid the checks in some cases and that
probably is preferable for Find. Afetr all, the only requirement is to get the
right answer.

* If the container is empty, you never have to make a call-back to determine the
answer, so you can avoid settting tampering. And given that changing the
tampering counter(s) means at least a increment/decrement pair (2 reads and 2
writes), it's certainly cheaper to make a pre-test to avoid those writes. For
other cases, like the iterator object, a similar situation applies (you're not
going to iterate anything, so no tampering calls can be made).

* If the container has exactly one element, you don't need a tampering check,
either, because the single call-out you will do will uniquely determine the
answer and you will have no future need to look at the container again after
that call. In that case, you don't need a tampering check on that single call.
This certainly would work for Find and "=", and possibly iterators as well.

* It might be possible to extend the technique used for a single element to
multiple elements, if you can make the result is just the combination of
call-outs without reference to the container after the call-outs. If the
elements are small, copying them into temporaries would have this effect.
Alternatively, one could save access-to-elements for every element to be checked
initially; you'd have to check somehow that the elements still exist before
using them in a call-out, but you wouldn't need to worry about other tampering
(additions/changes). Not sure that such a technique would be worth it, but
perhaps it would be cheaper for small numbers of elements.

Hope this helps.

***************************************************************


Questions? Ask the ACAA Technical Agent