There is the time of signature, and there is the time of verification. Let's first simplify the situation: we assume that the current date is 2009-07-08. For that value of "right now", the RootCA and SubCA certificates are still valid, but Alice's certificate is not. You see a signature which is purported to have been produced by Alice on 2009-05-01.
If you try to validate Alice's certificate, you will find it to be "expired" and, per X.509, that's the end of the story (section 6.1.3, step a.2). Possibly, there could exist a proof that the signature already existed at a past date, e.g. 2009-05-02; time stamps can be such proofs. At that date, Alice's certificate was still valid, so you could virtually imagine yourself looking at the signature and the certificates on 2009-05-02, and running the validation algorithm at that time. If you were convinced of the signature validity at that time, you would still remember it now. This is the basis of past validation.
But can you really time-travel like that ? There's the trouble with revocation. In a generic way, how would you know if Alice's private key was stolen ? Imagine that, on 2009-04-15, an evil individual (let's call him Albert) purloined Alice's key. Surely, a signature computed with that key on 2009-05-01 cannot be undoubtedly attributed to Alice, since Albert could have computed the same. In X.509, information about stolen keys ("compromised keys" in X.509 parlance) is distributed through revocation. The CRL published by SubCA would include Alice's certificate with a "revocation date" of 2009-04-15 (the theft might have been discovered only a few days later, but the CRL format includes a field which state the cut-off date). Now is the tricky point: a CRL produced at date T includes information about certificates which are still valid (as per "validity dates") at date T. On 2009-07-08, the CRL currently published by SubCA does not include Alice's certificate because Alice's certificate is expired, and you cannot know if it was revoked at some point or not.
Therefore, for past validation, you need more than a time stamp on the signature; you also need a time stamp on some revocation objects (CRL, OCSP responses...) which were issued while Alice's certificate was not expired yet.
In the discussion above, you see the two essential tools:
- Time stamps allow for some forms of time travel, in which you envisioned yourself at a past date, operating over some values (signatures, certificates,...) which are proven to exist since that date.
- Revocation is the way you are made aware of key compromises.
If we now consider ourselves to be on 2010-02-01, we have two extra layers of complexity:
- SubCA's certificate has also expired. So you need to mind the possibility of a theft of SubCA's key as well. This is the same problem, one level up: SubCA's certificate is considered as valid because it was signed by the root CA.
- RootCA's certificate has also "expired". This is a root CA, so it is not really a "certificate" (by whom is it certified ?), but some a priori trusted information about a name and a public key. If RootCA has an expiry date, then this means that beyond that date, you consider that you would not necessarily be made aware if the root private key was compromised. Strictly speaking, beyond that date, you have no trust whatsoever, therefore you lost.
All the validation "models" are just elaborate ways to dance around these issues, by ignoring some possibilities of key compromise. For instance, one would consider that a theft of the root's private key would be known anyway, even beyond the formal root "expiry", and that the end-of-life date for the root is just an administrative matter. If you begin to ignore some possible security issues, depending on a so-called "model", then it is not surprising that some signatures will be considered valid, or not valid, depending on the model.
Yet, as presented, your problem is very incomplete since it says nothing about time stamps, CRL, and time stamps on CRL.