Opened 3 years ago

Closed 2 years 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
branch-diff, diff-cov, branch-cov, buildbot
Author: rwall

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 3 years 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 3 years 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 3 years 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 3 years 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 3 years 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 3 years 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 2 years 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 2 years 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.