Opened 13 months ago

Closed 6 months ago

#6672 enhancement closed fixed (fixed)

Implement Serial Number Arithmetic from RFC1982 for comparison of DNS serial numbers and RRSIG inception dates

Reported by: rwall Owned by: rwall
Priority: normal Milestone: DNSSEC_Client
Component: names Keywords: edns
Cc: Branch: branches/serial-number-arithmetic-6672
(diff, github, buildbot, log)
Author: rwall Launchpad Bug:

Description (last modified by rwall)

In order to implement #6665 properly we will need a mechanism for
doing RFC1982 Serial Number Arithmetic.

This can also be used in t.n.secondary.SecondaryAuthority to properly
check that serial numbers incremented.

BobNovas has already done most of the work in:

It just needs tidying up.

https://tools.ietf.org/html/rfc4034#section-3.1.5

The Signature Expiration and Inception fields specify a validity
period for the signature. The RRSIG record MUST NOT be used for
authentication prior to the inception date and MUST NOT be used for
authentication after the expiration date.

The Signature Expiration and Inception field values specify a date
and time in the form of a 32-bit unsigned number of seconds elapsed
since 1 January 1970 00:00:00 UTC, ignoring leap seconds, in network
byte order. The longest interval that can be expressed by this
format without wrapping is approximately 136 years. An RRSIG RR can
have an Expiration field value that is numerically smaller than the
Inception field value if the expiration field value is near the
32-bit wrap-around point or if the signature is long lived. Because
of this, all comparisons involving these fields MUST use "Serial
number arithmetic", as defined in [RFC1982]. As a direct
consequence, the values contained in these fields cannot refer to
dates more than 68 years in either the past or the future.

See also:

Change History (8)

comment:1 Changed 13 months ago by rwall

  • Description modified (diff)
  • Owner set to rwall
  • Status changed from new to assigned

Some more links to existing implementations in bind9 and bind10.

comment:2 Changed 13 months ago by rwall

  • Author set to rwall
  • Branch set to branches/serial-number-arithmetic-6672

(In [39498]) Branching to 'serial-number-arithmetic-6672'

comment:3 Changed 13 months ago by rwall

  • Keywords review added
  • Owner rwall deleted
  • Status changed from assigned to new

Ready for review in log:branches/serial-number-arithmetic-6672

  1. Imported The SNA code from #5454
  2. Renamed various variables and functions.
  3. Added missing docstrings.
  4. Cleaned up whitespace
  5. Added some missing coverage
  6. Made the serialBits configurable, which allowed me to...
  7. Add tests for the example calculations in RFC1982
    1. One test in test_surprisingAddition didn't do what I expected and I'd like a second opinion on it.
  8. I've added various XXX comments for things which I don't fully understand or for things (tests) which I think are unnecessary.
  9. Build results:
    1. https://buildbot.twistedmatrix.com/boxes-supported?branch=/branches/serial-number-arithmetic-6672&num_builds=5
    2. There are various known twistedchecker false warnings.

comment:4 follow-up: Changed 10 months ago by exarkun

  • Keywords review removed
  • Owner set to rwall

Thanks for working on this rwall (and thanks again to BobNovas for the original contribution).

  1. twisted/names/util.py
    1. I'd like to think about a better name for the new module. There are some util and utils modules elsewhere in Twisted but these are all mistakes. *Everything* in Twisted is a utility for *something*. :) Perhaps twisted.names.serialnumber (or even twisted.names.rfc1982 - though this is opaque, at least once you understand it you know exactly what to expect).
    2. The module should define __all__.
    3. The SNA class attribute serialBits seems redundant with the instance attribute set by __init__.
    4. I think we've abandoned the use of @author (the only time I remember seeing it in the last 5 years is when someone submits a patch that deletes it).
    5. _modulo, halfRing, maxAdd are undocumented
    6. There's an __int__ special method that might be a better way to expose the asInt functionality.
    7. Can the implementation use the datetime module instead of the time module?
    8. The rich comparison methods should probably type check their argument and return NotImplemented if it is not a SNA. This way the TypeError-generating logic provided by the runtime will be invoked instead of an implementation-dependent AttributeError.
    9. The implementations of __lt__ and __gt__ don't need the self != sna2 condition in order to pass all of the unit tests. Logically, I don't see how it could make a difference to the result either.
    10. Maybe the explanation of ArithmeticError from __add__ could be more explicit in explaining that this is an exception because the operation isn't allowed by the specification. Or put another way... I think the documentation should explain something beyond what could be learned by reading the implementation. :) Documentation for the maxAdd attribute might help this situation as well.
    11. raise ArithmeticError() instead of raise ArithmeticError
    12. There's some extra whitespace inside the SNA() call in __add__
    13. snaMax doesn't seem to offer much beyond what max offers - particularly since it doesn't deal with the tricky non-transitiveness of less than/greater than as defined on serial numbers1. I'm not sure what the benefit of its None handling is. In other words, your comment in the test module seems pretty on-target to me. Maybe this code should go.
    14. RFC 4034 says: "The Signature Expiration Time and Inception Time field values MUST be represented either as an unsigned decimal integer indicating seconds since 1 January 1970 00:00:00 UTC, or in the form YYYYMMDDHHmmSS in UTC". Is there any reason for DateSNA.fmt to be public?
    15. Also _timeFormat might be a more descriptive name than _fmt. :)
    16. I don't think any new code should use str. Use either bytes or unicode. (There are exceptions but they mostly have to do with metaprogramming, I think - ie, cases where the type is related to something inherent to Python itself, such as the type of the keys in **kwargs accepted by a function ... or the behavior of __str__). Similarly, "" literals should probably be avoided in favor of either b"" or u"" (or b"" and __future__.unicode_literals).
    17. What do you think about making DateSNA not a SNA subclass? (Boooo subclassing boo)
  2. twisted/names/test/test_util.py
    1. There's a lot of similarity between these tests for the ordering implementation and other tests for ordering implementations. I'm sad we still haven't factored out a helper for this. Can you file a ticket for doing this and for refactoring the few places in Twisted that would benefit from such a helper (twisted.internet.test.test_base at least)?
    2. assertUndefinedComparison - I wonder about the choice to expose the undefined behavior in this subtle way instead of in some more obvious way. If some code performs a comparison with undefined behavior it will be very difficult for anyone to realize this is happening. It seems like raising an exception would be a better thing to do.
  3. Are you looking for feedback on the XXXs or are you just waiting to address them until the rest of the code is in good shape? I mostly skimmed past these but I can revisit them with more attention if that would be helpful.
  4. Is there somewhere in Twisted Names that could already benefit from this new code? Perhaps twisted.names.authority.getSerial (though this is obscure and I doubt the benefit will be significant. twisted.named.cache seems like the other place where it could be helpful but it looks like that code is all very naive and extending it to handle serial numbers properly is probably too large a task to tack on to this ticket.

Please re-submit when these points have been addressed. Thanks.

1

>>> a = SNA(0)                                                                                                   
>>> b = a + SNA(2 ** 31 - 1)                                                                                     
>>> c = b + SNA(1)                                                                                               
>>> print snaMax([a, b, c])                                                                                      
2147483648
>>> print snaMax([a, c, b])
2147483647
>>> print max(a, b, c)
2147483648
>>> print max(a, c, b)
2147483647
>>> 

comment:5 in reply to: ↑ 4 ; follow-up: Changed 10 months ago by rwall

  • Keywords review added
  • Owner rwall deleted

Thanks for the review.

I've addressed most of the comments I think. One or two I was unsure of or
disagreed with.

Some more discussion and answers below.

Replying to exarkun:
<snip>

  1. The rich comparison methods should probably type check their argument and return NotImplemented if it is not a SNA. This way the TypeError-generating logic provided by the runtime will be invoked instead of an implementation-dependent AttributeError.

r40633

We discussed this on IRC, but I think I prefer to raise an explicit
TypeError. Here's why.

Returning NotImplemented from lt always seems to return True and False from
gt. Due to some fallback comparison mechanism in Python I think.

Python 2 is more stubborn and when NotImplemented is returned or no hooks have
been implemented, the C code ends up in the default_3way_compare() C function,

I think this may cause people to think that Int and SNA can be reliably
compared...they can't.

I decided to raise TypeError instead. This makes it clear that you can only
compare SNA with SNA.

  1. The implementations of __lt__ and __gt__ don't need the `self != sna2` condition in order to pass all of the unit tests. Logically, I don't see how it could make a difference to the result either.

r40634

I also removed some unnecessary brackets which I think makes the code clearer.

r40635 Also added ne which is important.

  1. Maybe the explanation of ArithmeticError from __add__ could be more explicit in explaining that this is an exception because the operation isn't allowed by the specification. Or put another way... I think the documentation should explain something beyond what could be learned by reading the implementation. :) Documentation for the maxAdd attribute might help this situation as well.
  2. raise ArithmeticError() instead of raise ArithmeticError
  3. There's some extra whitespace inside the SNA() call in __add__

r40636

Also found the bug causing an unexplained failure in test_surprisingAddition.

r40638 Also added a clear error message for this case.

  1. I don't think any new code should use str. Use either bytes or unicode. (There are exceptions but they mostly have to do with metaprogramming, I think - ie, cases where the type is related to something inherent to Python itself, such as the type of the keys in **kwargs accepted by a function ... or the behavior of __str__). Similarly, "" literals should probably be avoided in favor of either b"" or u"" (or b"" and __future__.unicode_literals).

r40641. I tried using unicode_literals but then reverted it after discussion
with lvh on IRC and also because it caused problems with FancyStrMixin which
expects showAttributes to contain strings. That's probably a bug.

r40643. Returned nativeString from str methods.

r40644 Also added the new modules to setup3.py and test pass on Python3 builder.

  1. What do you think about making DateSNA not a SNA subclass? (Boooo subclassing boo)

r40646

I looked at DateSNA and decided it was overkill anyway. All we're going to need
for RRSIG is a convenient way to convert to and from RFC4034 date strings, so I
added a couple of methods to SNA and removed DateSNA.

And in doing that, I have better understood the Y2038 and Y2106 date wrapping
problems and updated the tests accordingly.

Also encountered a problem on the 32bit build slaves...I think because their
datetime modules use signed 32bit ints under the hood and can't store the full
32bit unsigned range of timestamps in an SNA.

  1. twisted/names/test/test_util.py
  1. There's a lot of similarity between these tests for the ordering implementation and other tests for ordering implementations. I'm sad we still haven't factored out a helper for this. Can you file a ticket for doing this and for refactoring the few places in Twisted that would benefit from such a helper (twisted.internet.test.test_base at least)?

Having removed the DateSNA subclass, there isn't so much duplication in this
module.

Some related things which I am aware of / found:

  • twisted.python.compat.comparable
  • twisted.test.testutils.ComparisonTestsMixin.assertNormalEqualityImplementation

I haven't created a ticket because I'm not really sure how to describe the
problem.

  1. assertUndefinedComparison - I wonder about the choice to expose the undefined behavior in this subtle way instead of in some more obvious way. If some code performs a comparison with undefined behavior it will be very difficult for anyone to realize this is happening. It seems like raising an exception would be a better thing to do.

I'm not sure about this. I agree that it is non-obvious, but equally, I don't
think you'd want an exception to unexpectedly bring down your nameserver because
of a rare combination of serial numbers in a zone or expiration dates in an
RRSIG record.

I think I can do it, by checking if the supplied value is equal to _halfRing.

But how about logging a warning instead of raising an Exception?

  1. Are you looking for feedback on the XXXs or are you just waiting to address them until the rest of the code is in good shape? I mostly skimmed past these but I can revisit them with more attention if that would be helpful.

I've removed most / all of them now I think. Mostly because I think I've
answered or addressed them while addressing the code review points.

  1. Is there somewhere in Twisted Names that could already benefit from this new code? Perhaps twisted.names.authority.getSerial (though this is obscure and I doubt the benefit will be significant. twisted.named.cache seems like the other place where it could be helpful but it looks like that code is all very naive and extending it to handle serial numbers properly is probably too large a task to tack on to this ticket.

The obvious place is twisted.names.secondary.SecondaryAuthority. It should be
using Serial Number Arithmetic to compare the serial numbers of the local and
master zone before doing a zone transfer. I'll create a ticket about that when
this gets merged.

I've decided to make SNA private until it's proved its usefulness.

-RichardW.

comment:6 in reply to: ↑ 5 ; follow-up: Changed 6 months ago by glyph

  • Keywords review removed
  • Owner set to rwall

Thanks for getting this to completion; it looks pretty good. Thanks especially for 100% branch coverage :-).

One thing I really don't like is the docstring. An SNA is not a "helper class". ("Helper" is right up there with manager/processor/handler in terms of a non-word, and a class docstring should never contain the word "class"). An SNA is a value of some kind, and it should describe that value.

My preference would be to change the class's name, too, to be something like SerialNumber. What do you think?

Land as you like (ideally after fixing the couple of pydoctor reference errors and the test things called out below), and hopefully the inline commentary will provide the feedback you were looking for.

Replying to rwall:

Thanks for the review.

I've addressed most of the comments I think. One or two I was unsure of or
disagreed with.

Some more discussion and answers below.

Replying to exarkun:
<snip>

  1. The rich comparison methods should probably type check their argument and return NotImplemented if it is not a SNA. This way the TypeError-generating logic provided by the runtime will be invoked instead of an implementation-dependent AttributeError.

r40633

The test docstrings in this change still refer to comparisons returning False where they're clearly raising TypeError instead.

I decided to raise TypeError instead. This makes it clear that you can only
compare SNA with SNA.

Can you raise this as an issue on the mailing list? I'm inclined to agree with you but it would be nice if we had some consensus among Twisted contributors about TypeError vs. NotImplemented while we are in this perpetual Python3 netherworld.

r40634

I also removed some unnecessary brackets which I think makes the code clearer.

r40635 Also added ne which is important.

Shouldn't the __ne__ be implementable without re-typing the whole algorithm?

  1. I don't think any new code should use str. Use either bytes or unicode. (There are exceptions but they mostly have to do with metaprogramming, I think - ie, cases where the type is related to something inherent to Python itself, such as the type of the keys in **kwargs accepted by a function ... or the behavior of __str__). Similarly, "" literals should probably be avoided in favor of either b"" or u"" (or b"" and __future__.unicode_literals).

r40641. I tried using unicode_literals but then reverted it after discussion
with lvh on IRC and also because it caused problems with FancyStrMixin which
expects showAttributes to contain strings. That's probably a bug.

As exarkun said about metaprogramming though, it's kind of a special case. In this case, do whatever you think works, but generally, moving to as many __future__ imports as possible, especially unicode_literals, makes things easier. For integration with metaprogramming or older code, explicitly using nativeString would be better.

Even more generally, FancyStrMixin and FancyEqMixin are both kind of not fantastic code. Both are trying to facilitate the easy creation and runtime understanding of value types, but there are numerous deficiencies in their implementation.

r40643. Returned nativeString from str methods.

Huh, I guess that's the right thing to do there, yeah.

r40644 Also added the new modules to setup3.py and test pass on Python3 builder.

Thanks. (Gosh I wish we had wildcards in there so we wouldn't need to keep doing this.)

Also encountered a problem on the 32bit build slaves...I think because their
datetime modules use signed 32bit ints under the hood and can't store the full
32bit unsigned range of timestamps in an SNA.

Did you manage to work around this? Buildbots look to be in good shape, so I'm guessing "yes" but I don't see the solution anywhere obvious. (Please be sure to address before landing.)

Some related things which I am aware of / found:

  • twisted.python.compat.comparable
  • twisted.test.testutils.ComparisonTestsMixin.assertNormalEqualityImplementation

I haven't created a ticket because I'm not really sure how to describe the
problem.

A ticket for using these facilities, you mean?

But how about logging a warning instead of raising an Exception?

I'd prefer to work backwards in cases like this. Who is supposed to notice this? An administrator? So they notice the warning. How are they supposed to act on it? Maybe it should be something other than logging, I don't know. Values outside these ranges seem like bad data to me, but I don't know how to identify the provenance of the bad data in a way an admin could easily act upon.

I've removed most / all of them now I think. Mostly because I think I've
answered or addressed them while addressing the code review points.

test_maxVal: "I've got a feeling we need more tests…"

Searching the diff and github diff links above could be helpful. ;-)

comment:7 in reply to: ↑ 6 Changed 6 months ago by rwall

  • Milestone set to DNSSEC_Client
  • Status changed from new to assigned

Replying to glyph:

Thanks for getting this to completion; it looks pretty good. Thanks
especially for 100% branch coverage :-).

One thing I really don't like is the docstring. An SNA is not a "helper
class". ("Helper" is right up there with manager/processor/handler in terms
of a non-word, and a class docstring should never contain the word "class").
An SNA is a value of some kind, and it should describe that value.

Done. r41745

My preference would be to change the class's name, too, to be something like
SerialNumber. What do you think?

Done. r41746

Land as you like (ideally after fixing the couple of pydoctor reference errors

Done. r41746 fixes these too I think.

and the test things called out below), and hopefully the inline commentary
will provide the feedback you were looking for.

Thanks again Glyph. I've added some more responses below.

I'll start a new build and merge if the results are green.

-RichardW.

Replying to rwall:

r40633

The test docstrings in this change still refer to comparisons returning False
where they're clearly raising TypeError instead.

Done. r41747

I decided to raise TypeError instead. This makes it clear that you can only
compare SNA with SNA.

Can you raise this as an issue on the mailing list? I'm inclined to agree
with you but it would be nice if we had some consensus among Twisted
contributors about TypeError vs. NotImplemented while we are in this perpetual
Python3 netherworld.

https://twistedmatrix.com/pipermail/twisted-python/2014-February/028079.html

No responses yet.

r40634
I also removed some unnecessary brackets which I think makes the code clearer.
r40635 Also added ne which is important.

Shouldn't the __ne__ be implementable without re-typing the whole algorithm?

Done. r41748

  1. I don't think any new code should use str. Use either bytes or unicode. (There are exceptions but they mostly have to do with metaprogramming, I think - ie, cases where the type is related to something inherent to Python itself, such as the type of the keys in **kwargs accepted by a function ... or the behavior of __str__). Similarly, "" literals should probably be avoided in favor of either b"" or u"" (or b"" and __future__.unicode_literals).

r40641. I tried using unicode_literals but then reverted it after discussion
with lvh on IRC and also because it caused problems with FancyStrMixin which
expects showAttributes to contain strings. That's probably a bug.

As exarkun said about metaprogramming though, it's kind of a special case. In
this case, do whatever you think works, but generally, moving to as many
__future__ imports as possible, especially unicode_literals, makes things
easier. For integration with metaprogramming or older code, explicitly using
nativeString would be better.

I'm going to leave this. I still don't fully understand the implications of
using unicode_literals.

Even more generally, FancyStrMixin and FancyEqMixin are both kind of not
fantastic code. Both are trying to facilitate the easy creation and runtime
understanding of value types, but there are numerous deficiencies in their
implementation.

I discussed this with Tom and JP at the Bristol sprint in December. We agreed
that FancyStrMixin and FancyEqMixin could be re-implemented as class decorators
and made more flexible at the same time. I see that you already a created a
ticket for improvements to FancyEqMixin and FancyStringMixin so I'll just link that ticket here and
link back to this comment in that ticket.

See #6529

Did you manage to work around this? Buildbots look to be in good shape, so
I'm guessing "yes" but I don't see the solution anywhere obvious. (Please be
sure to address before landing.)

I fixed this with a comment in r40654.

Some related things which I am aware of / found:

  • twisted.python.compat.comparable
  • twisted.test.testutils.ComparisonTestsMixin.assertNormalEqualityImplementation

I haven't created a ticket because I'm not really sure how to describe the
problem.

A ticket for using these facilities, you mean?

I spoke to exarkun yesterday and created a ticket for adding an API for testing equality and ordering of objects which provide rich comparison methods

But how about logging a warning instead of raising an Exception?

I'd prefer to work backwards in cases like this. Who is supposed to notice
this? An administrator? So they notice the warning. How are they supposed
to act on it? Maybe it should be something other than logging, I don't know.
Values outside these ranges seem like bad data to me, but I don't know how to
identify the provenance of the bad data in a way an admin could easily act
upon.

I'm going to postpone this until I actually get round to using SerialNumber in
anger. I do agree; SerialNumber shouldn't be responsible for logging such
warnings. But neither am I sure that it should raise an exception. That means
that every SerialNumber comparison would have to be wrapped in a try / except
block. I suppose that's already the case for the ArithmeticError raised by
add.

I've removed most / all of them now I think. Mostly because I think I've
answered or addressed them while addressing the code review points.

test_maxVal: "I've got a feeling we need more tests…"

Searching the diff and github diff links above could be helpful. ;-)

Aha! Thanks for spotting that. Removed in r41749.

comment:8 Changed 6 months ago by rwall

  • Resolution set to fixed
  • Status changed from assigned to closed

(In [41756]) Merge serial-number-arithmetic-6672

Author: BobNovas, rwall
Reviewers: exarkun, glyph
Fixes: #6672
Refs: #5454, #6665

A private Serial Number Arithmetic module for manipulating Serial Numbers
defined in RFC1982. This will be used for comparison of DNS zone serial numbers
and RRSIG inception dates.

Note: See TracTickets for help on using tickets.