Question about "happens-before" and reordering

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

Question about "happens-before" and reordering

robertkuhar
At a JavaOne session today entitled "Secure Coding Antipatterns:  Avoiding
Vunerabilities" the following code snippet was presented.

  Antipattern 6: Believing a Constructor Exception Destroys the Object
  Problem
    Throwing an exception from a constructor does not prevent a partially
    initialized instance from being acquired
      - Attacker can override finalize method to obtain the object

To solve this problem, they presented the following snippet and explanation:

  Secure Coding Guidelines:
    - If finalize method can be overridden, ensure partially initialized
      instances are unusable
    - Do not set fields until all checks have completed
    - Use an initialized flag

  public class ClassLoader {
    private boolean initialized = false;
    ClassLoader() {
      securityCheck(); // can throw an Exception
      init();
      initialized = true; // check flag in all relevant methods
    }
  }

I asserted that they had two problems with this code.  As I understand it, the
runtime is free to reorder the instructions in this constructor.  This means
that initialized=true may occur before the calls to either securityCheck() or
init().  If that is the case, its value cannot be trusted as this code stands
now.

Second, even if initialized boolean field gets set correctly, the fact that it
is not covered by any synchronization or volatile means that any thread
(remember, the problem they are trying to solve has to do with malicious
finalizer code) other than the one that new'ed this kid up, may not see the
current value of the initialized boolean field.  Garbage Collection usually
runs on its own thread, no?

It is my opinion that this code is not thread-safe.

The reply was that somehow the Exception that can come out of securityCheck()
establishes some "happens-before" and therefore this code is thread-safe.  I am
skeptical as I have never heard that before (or didn't understand it if I did).

Point by point how right or wrong am I and why.

Thanks.

Bob


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" and reordering

Giuliano Mega
Hi,

> The reply was that somehow the Exception that can come out of securityCheck()
> establishes some "happens-before" and therefore this code is thread-safe.  I am
> skeptical as I have never heard that before (or didn't understand it if I did).

The language spec says that there is a happens-before edge that goes
from the end of the constructor to the start of the finalizer of that
same object. (see
http://java.sun.com/docs/books/jls/third_edition/html/memory.html#17.4.5)

So, unless I'm talking nonsense (in which case I would politely ask
for someone to correct me), this means that what happens at the
constructor must be visible at the finalizer, for all threads.
Although the instructions may be reordered, the resulting execution
must be "legal" in the sense that it must reflect a possible
execution. In your example, if an exception is thrown at the security
check, then the flag must be seen as false at the finalizer as it is
the only legal option.

Best,

--
Giuliano Mega <[hidden email]>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" and reordering

Giuliano Mega
> So, unless I'm talking nonsense (in which case I would politely ask
> for someone to correct me), this means that what happens at the
> constructor must be visible at the finalizer, for all threads.
> Although the instructions may be reordered, the resulting execution
> must be "legal" in the sense that it must reflect a possible
> execution. In your example, if an exception is thrown at the security
> check, then the flag must be seen as false at the finalizer as it is
> the only legal option.

I'm sorry for posting again, but I just re-read my answer and found it
confusing. What I wanted to say is that the reordering that occurs
inside of the constructor must respect local ordering within a single
thread of control, and that the changes that were performed by the
constructor must have been already commited to main memory when the
finalizer begins, or the constructor won't appear to have
happenned-before the finalizer (and the spec says it must).

Best,

--
Giuliano Mega <[hidden email]>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" andreordering

Thomas Hawtin
In reply to this post by robertkuhar
Robert Kuhar wrote:
>   Secure Coding Guidelines:
>     - If finalize method can be overridden, ensure partially initialized
>       instances are unusable

I think it's a little more subtle than that, particularly prior to 1.6.

>   public class ClassLoader {
>     private boolean initialized = false;

I think the "= false" bit here is misleading. I certainly would not want
to see "= true" in a similar situation.

>     ClassLoader() {
>       securityCheck(); // can throw an Exception
>       init();
>       initialized = true; // check flag in all relevant methods
>     }
>   }
>
> I asserted that they had two problems with this code.  As I understand it, the
> runtime is free to reorder the instructions in this constructor.  This means
> that initialized=true may occur before the calls to either securityCheck() or
> init().  If that is the case, its value cannot be trusted as this code stands
> now.

If securityCheck does throw an exception, then the initialized = true
statement must never be executed. So there is no security problem there.

If securityCheck does not throw, then theoretically you could see a
non-working, partially-initialised instance. However, that would be your
own fault.

Tom Hawtin
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" andreordering

Pete.Soper
Thomas Hawtin wrote:

> Robert Kuhar wrote:
>
>>   Secure Coding Guidelines:
>>     - If finalize method can be overridden, ensure partially
>> initialized       instances are unusable
>
>
> I think it's a little more subtle than that, particularly prior to 1.6.
>
>>   public class ClassLoader {
>>     private boolean initialized = false;
>
>
> I think the "= false" bit here is misleading. I certainly would not want
> to see "= true" in a similar situation.
>
>>     ClassLoader() {
>>       securityCheck(); // can throw an Exception
>>       init();
>>       initialized = true; // check flag in all relevant methods
>>     }
>>   }
>>
>> I asserted that they had two problems with this code.  As I understand
>> it, the
>> runtime is free to reorder the instructions in this constructor.  This
>> means
>> that initialized=true may occur before the calls to either
>> securityCheck() or
>> init().  If that is the case, its value cannot be trusted as this code
>> stands
>> now.
>
>
> If securityCheck does throw an exception, then the initialized = true
> statement must never be executed. So there is no security problem there.

Because compilers are not free to do this kind of code motion? In the
old 3GL days, compilers for some languages were free to determine if an
initialized reference (or maybe an extremely subtle alias for the same
storage) is possible in the called routine and, if not, hoist the
assignment up for the sake of better instruction scheduling, getting it
out of a loop, etc.

I don't recall if it was mentioned that init is assumed to be a method
of ClassLoader with the body judged irrelevant to show. If init is a
method of ClassLoader, then the compiler (the dynamic one we typically
enjoy, not javac) is free to determine if init can assign to
initialized, I think. (If it's free to suck the code inline, then it's
surely OK to treat it like just another set of statements).

But it seems impossible for securityCheck to be able to assign to
initialized by any means, as it can't have a reference to the object
being constructed. So the init call is the barrier to code motion, I
think. But I don't know for sure and the compiler writer that sits next
door to me is at J1.

Cliff would know.

-Pete

>
> If securityCheck does not throw, then theoretically you could see a
> non-working, partially-initialised instance. However, that would be your
> own fault.
>
> Tom Hawtin
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" andreordering

Pete.Soper
Pete Soper wrote:
> But it seems impossible for securityCheck to be able to assign to
> initialized by any means, as it can't have a reference to the object
> being constructed. So the init call is the barrier to code motion, I

I meant potential barrier.

-Pete

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" and reordering

Pete.Soper
In reply to this post by Giuliano Mega
Giuliano Mega wrote:

>> So, unless I'm talking nonsense (in which case I would politely ask
>> for someone to correct me), this means that what happens at the
>> constructor must be visible at the finalizer, for all threads.
>> Although the instructions may be reordered, the resulting execution
>> must be "legal" in the sense that it must reflect a possible
>> execution. In your example, if an exception is thrown at the security
>> check, then the flag must be seen as false at the finalizer as it is
>> the only legal option.
>
>
> I'm sorry for posting again, but I just re-read my answer and found it
> confusing. What I wanted to say is that the reordering that occurs
> inside of the constructor must respect local ordering within a single
> thread of control, and that the changes that were performed by the
> constructor must have been already commited to main memory when the
> finalizer begins, or the constructor won't appear to have
> happenned-before the finalizer (and the spec says it must).

This seemed quite clear the first time. More fundamentally, if the
constructor never completes, the finalizer's running is impossible, right?

>
> Best,
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" andreordering

Thomas Hawtin
Pete Soper wrote:
>
> This seemed quite clear the first time. More fundamentally, if the
> constructor never completes, the finalizer's running is impossible, right?

JLS 3 states that the finaliser may (because it never must) run if the
Object constructor exited normally. 1.6 complies with this (apparently
even if instrumentation rewrites the Object constructor).

I believe earlier editions of the JLS are silent on this. 1.5 (and I
presumably earlier versions) will call the finaliser on any object that
has been allocated. Possibly not even calling the derived most
constructor. IIRC, javac produced byte code does the new, dups the
uninitialised reference, evaluates the arguments, then calls the
<init>(...)V, so even if the arguments are not fully evaluated the
finaliser is called.

http://www.mernst.org/blog/archives/03-01-2006_03-31-2006.html#46
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4034630

Tom Hawtin
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" and reordering

robertkuhar
In reply to this post by Giuliano Mega
> This seemed quite clear the first time. More fundamentally, if the
> constructor never completes, the finalizer's running is impossible, right?
>
The finalizer running in either the success or failure of the constructor is
the vunerability the example is trying to solve.  Somewhere on the show-floor,
as I was running around trying to gain enlightenment, the assertion was made
that the root cause of this problem is exactly that; the constructor failed,
but the object existed for the GC to find and finalize.

It appears that what makes the example thread-safe is a special case of the
relationship between the constructor and the finalizer of which I was unaware.

  "...or the constructor won't appear to have happenned-before the finalizer
(and the spec says it must)." - Giuliano Mega
So that now makes sense.  However, it still strikes me as odd that a similar
pattern is held up as "what not to do" in the discussions of double-checked
locking but, for this case of constructor to finalizer, is somehow correct.

What I really need is "the Visible VM".  Much like "the Visible V8" of my
childhood.  You can do things to it, and watch the effects directly rather than
theorize about what can happen.  Now that would be really useful.

Thanks to all for their replies.  I think I'll just make my classes final and
that's that.  No need to worry about malicious subclasses exploiting finalizer
behavior.  Inheritence be damned!  I'm joking, I like inheritence.

Bob


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" and reordering

Jeremy Manson
In reply to this post by robertkuhar
Robert Kuhar wrote:
> I asserted that they had two problems with this code.  As I understand it, the
> runtime is free to reorder the instructions in this constructor.  This means
> that initialized=true may occur before the calls to either securityCheck() or
> init().  If that is the case, its value cannot be trusted as this code stands
> now.

This is not the case.  In Java, exceptions are precise, and must be
treated like control flow.  The write will only occur if the exception
is not thrown.  Neither this thread nor any other can see a write that
does not occur.  This is one of those very few, tricky to get,
guarantees for programs with data races that we make.

So, the point that the speaker was probably trying to make, which is
that you can check the value of "initialized" to determine if
securityCheck() exited without throwing an exception, is perfectly valid.

The compiler is free to move the write to initialized early if it can
determine that the exception will not be thrown.  It is also free to
hoist it above the call to init() (depending on what init() actually
does).  This means that if another thread can obtain a reference to this
object via a data race, and reads the "initialized" variable, it can see
the value "true" even if the object is not fully constructed.
Alternatively, such a thread could see a value "false" for initialized
even if the object is fully constructed.

A few things to note:

0) Why isn't this class final?

1) As has been noted, constructors are guaranteed to happen-before
finalize methods.  Therefore, finalizers will see all the writes that
occur in the constructor.  For the purposes of whether this code does
what it is intended to do, though, this is irrelevant, because the
finalizer (I assume) is just resurrecting the object.

2) The initialized field should probably be final (which would mean that
you could not put the "initialized = false" line in, but you probably
don't want that line there anyway, as the default value is false, and
moving the constructor around / adding more constructors will cause
confusion).  Otherwise, you could use reflection to set it.

                                        Jeremy

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" and reordering

Jeremy Manson
Jeremy Manson wrote:

>
> 2) The initialized field should probably be final (which would mean that
> you could not put the "initialized = false" line in, but you probably
> don't want that line there anyway, as the default value is false, and
> moving the constructor around / adding more constructors will cause
> confusion).  Otherwise, you could use reflection to set it.
>

Whoops!  I didn't mean that last bit!  But it should probably be final
anyway.

                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" andreordering

Pete.Soper
In reply to this post by Thomas Hawtin
Thomas Hawtin wrote:

> Pete Soper wrote:
>
>>
>> This seemed quite clear the first time. More fundamentally, if the
>> constructor never completes, the finalizer's running is impossible,
>> right?
>
>
> JLS 3 states that the finaliser may (because it never must) run if the
> Object constructor exited normally. 1.6 complies with this (apparently
> even if instrumentation rewrites the Object constructor).
>
> I believe earlier editions of the JLS are silent on this. 1.5 (and I
> presumably earlier versions) will call the finaliser on any object that
> has been allocated. Possibly not even calling the derived most
> constructor. IIRC, javac produced byte code does the new, dups the
> uninitialised reference, evaluates the arguments, then calls the
> <init>(...)V, so even if the arguments are not fully evaluated the
> finaliser is called.
>
> http://www.mernst.org/blog/archives/03-01-2006_03-31-2006.html#46
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4034630

  This is a dupe of 5092933 which I'm happy to say was fixed in build 59
of Mustang.
   JLS 17.4.5 says the edge is from the end of the constructor, which
presumably can't be reached if an exception is thrown or the thread
stops making progress through the constructor. If a more tricky
definition of "end" is being used, then I shouldn't be surprised, but
will be anyway.

-Pete

>
> Tom Hawtin
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" andreordering

Jeremy Manson
Pete Soper wrote:

>   JLS 17.4.5 says the edge is from the end of the constructor, which
> presumably can't be reached if an exception is thrown or the thread
> stops making progress through the constructor. If a more tricky
> definition of "end" is being used, then I shouldn't be surprised, but
> will be anyway.

The section on finalization to which 17.4.5 points clarifies this to
mean that the constructor's "completion" happens-before the finalize
method.  In the context of the JLS, "completion" means completion via
normal means or via exceptional (also called abrupt) means.

So "end" here means via an exception, as well.  We probably should have
used the word "completion" in 17.4.5 to make it clearer.

OTOH, if the thread hangs, then completion is never reached, as you
point out.

                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" and reordering

Pete.Soper
In reply to this post by robertkuhar
Robert Kuhar wrote:
>>This seemed quite clear the first time. More fundamentally, if the
>>constructor never completes, the finalizer's running is impossible, right?
>>
>
> The finalizer running in either the success or failure of the constructor is
> the vunerability the example is trying to solve.  Somewhere on the show-floor,
> as I was running around trying to gain enlightenment, the assertion was made
> that the root cause of this problem is exactly that; the constructor failed,
> but the object existed for the GC to find and finalize.

I'm slow on the uptake some times (by approximately 7 1/2 years) and
missed understanding what started this mail thread. Thanks to Tom for
making the bug to do with this apparent, and to Jeremy for explaining
the exception handling (probably) being the big roadblock for preventing
the code motion in that example constructor.

And I just spotted Bill Pugh's comment about the older of the two bugs.
I do need something for my stomach.

-Pete

>
> It appears that what makes the example thread-safe is a special case of the
> relationship between the constructor and the finalizer of which I was unaware.
>
>   "...or the constructor won't appear to have happenned-before the finalizer
> (and the spec says it must)." - Giuliano Mega
> So that now makes sense.  However, it still strikes me as odd that a similar
> pattern is held up as "what not to do" in the discussions of double-checked
> locking but, for this case of constructor to finalizer, is somehow correct.
>
> What I really need is "the Visible VM".  Much like "the Visible V8" of my
> childhood.  You can do things to it, and watch the effects directly rather than
> theorize about what can happen.  Now that would be really useful.
>
> Thanks to all for their replies.  I think I'll just make my classes final and
> that's that.  No need to worry about malicious subclasses exploiting finalizer
> behavior.  Inheritence be damned!  I'm joking, I like inheritence.
>
> Bob
>
>
> __________________________________________________
> Do You Yahoo!?
> Tired of spam?  Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com 
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" andreordering

Pete.Soper
In reply to this post by Jeremy Manson
Jeremy Manson wrote:

> Pete Soper wrote:
>
>>   JLS 17.4.5 says the edge is from the end of the constructor, which
>> presumably can't be reached if an exception is thrown or the thread
>> stops making progress through the constructor. If a more tricky
>> definition of "end" is being used, then I shouldn't be surprised, but
>> will be anyway.
>
>
> The section on finalization to which 17.4.5 points clarifies this to
> mean that the constructor's "completion" happens-before the finalize
> method.  In the context of the JLS, "completion" means completion via
> normal means or via exceptional (also called abrupt) means.
>
> So "end" here means via an exception, as well.  We probably should have

Oh, so what I asserted to Tom is wrong. Thanks for this clarification.

If a finalizer method might run on an object for which construction is
incomplete in an arbitrary manner (by virtue of the ctor throwing an
exception), it means writing a good finalizer method is more challenging
than writing correct concurrent code for the uninitiated, or at least
just as challenging. It tells me if I ever get tempted to write a
finalizer method I'll put an edge between the last statement of the ctor
and the first statement of the finalizer as the first lines of code
written. And it's difficult to reconcile this with Bill Pugh's comment
about 4034630 on the page Tom pointed to. Is the JLS being updated for
Mustang to go along with the implementation change, or am I still not
getting it?

-Pete

> used the word "completion" in 17.4.5 to make it clearer.
>
> OTOH, if the thread hangs, then completion is never reached, as you
> point out.
>
>                     Jeremy
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Question about "happens-before" andreordering

Jeremy Manson
Pete Soper wrote:

> Oh, so what I asserted to Tom is wrong. Thanks for this clarification.
>
> If a finalizer method might run on an object for which construction is
> incomplete in an arbitrary manner (by virtue of the ctor throwing an
> exception), it means writing a good finalizer method is more challenging
> than writing correct concurrent code for the uninitiated, or at least
> just as challenging. It tells me if I ever get tempted to write a
> finalizer method I'll put an edge between the last statement of the ctor
> and the first statement of the finalizer as the first lines of code
> written.

Hopefully, you shouldn't be too tempted to write finalizer methods.
There is a reason we say that there is an edge from the end of the
constructor to the finalizer.  Uses of the object after completion of
the constructor are not guaranteed to happen-before the finalizer.  In
simpler terms, *the finalizer will not necessarily see updates that
occur to an object after the constructor completes*.  You can set a
field of that object, and the finalizer might not see it!

To get around this, you need a happens-before edge from the last use of
the object in the rest of the code to the finalizer.  I urge people
interested in writing finalizers to read Section 12.6.1 in JLS3.

Actually, I urge people interested in writing finalizers not to write
finalizers.

 > And it's difficult to reconcile this with Bill Pugh's comment
> about 4034630 on the page Tom pointed to. Is the JLS being updated for
> Mustang to go along with the implementation change, or am I still not
> getting it?
>

I had forgotten to mention that issue.  There is a special case to my
comments - the constructor for class Object needs to be invoked and
complete normally for finalization to occur at all.  Other constructors
may terminate by throwing exceptions.  The details are in JLS section 12.6.

Thanks for the clarification.

                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest