[v2] ntp: remove accidental integer wrap-around

Commit Message

Justin Stitt May 17, 2024, 8:22 p.m. UTC

Using syzkaller alongside the newly reintroduced signed integer overflow
sanitizer spits out this report:

UBSAN: signed-integer-overflow in ../kernel/time/ntp.c:461:16
9223372036854775807 + 500 cannot be represented in type 'long'
Call Trace:
 <IRQ>
 dump_stack_lvl+0x93/0xd0
 handle_overflow+0x171/0x1b0
 second_overflow+0x2d6/0x500
 accumulate_nsecs_to_secs+0x60/0x160
 timekeeping_advance+0x1fe/0x890
 update_wall_time+0x10/0x30
...

time_maxerror is unconditionally incremented and the result is checked
against NTP_PHASE_LIMIT, but the increment itself can overflow,
resulting in wrap-around to negative space.

The user can supply some crazy values which is causing the overflow. Add
an extra validation step checking that maxerror is reasonable.

Link: https://github.com/llvm/llvm-project/pull/82432 [1]
Closes: https://github.com/KSPP/linux/issues/354
Cc: [e-mail]
Signed-off-by: Justin Stitt <[e-mail]>
---
Changes in v2:
- update commit log (thanks Thomas)
- check for sane user input during validation (thanks Thomas)
- Link to v1: https://lore.kernel.org/r/[e-mail]
---

Historically, the signed integer overflow sanitizer did not work in the
kernel due to its interaction with `-fwrapv` but this has since been
changed [1] in the newest version of Clang. It was re-enabled in the
kernel with Commit 557f8c582a9ba8ab ("ubsan: Reintroduce signed overflow
sanitizer").

Here's the syzkaller reproducer:
| #{Threaded:false Repeat:false RepeatTimes:0 Procs:1 Slowdown:1 Sandbox:
| #SandboxArg:0 Leak:false NetInjection:false NetDevices:false
| #NetReset:false Cgroups:false BinfmtMisc:false CloseFDs:false KCSAN:false
| #DevlinkPCI:false NicVF:false USB:false VhciInjection:false Wifi:false
| #IEEE802154:false Sysctl:false Swap:false UseTmpDir:false
| #HandleSegv:false Repro:false Trace:false LegacyOptions:{Collide:false
| #Fault:false FaultCall:0 FaultNth:0}}
| clock_adjtime(0x0, &(0x7f0000000000)={0x5, 0x1, 0x40,
| 0x7fffffffffffffff, 0x8, 0xb2, 0x256, 0x6, 0x5, 0x8001, 0x9, 0x3f, 0x0,
| 0x8000, 0x800, 0x64d, 0x50000, 0x7ff, 0x8000000000000001, 0x1f, 0x3,
| 0xfff, 0x7fffffff, 0x5, 0x100, 0x4})

... which was used against Kees' tree here (v6.8rc2):
https://git.kernel.org/pub/scm/linux/kernel/git/kees/linux.git/log/?h=wip/v6.9-rc2/unsigned-overflow-sanitizer

... with this config:
https://gist.github.com/JustinStitt/824976568b0f228ccbcbe49f3dee9bf4
---
 kernel/time/timekeeping.c | 5 +++++
 1 file changed, 5 insertions(+)


---
base-commit: 0106679839f7c69632b3b9833c3268c316c0a9fc
change-id: 20240507-b4-sio-ntp-usec-1a3ab67bdce1

Best regards,
--
Justin Stitt <[e-mail]>

Comments

Thomas Gleixner May 24, 2024, 12:09 p.m. UTC | #1

On Fri, May 17 2024 at 20:22, Justin Stitt wrote:
> time_maxerror is unconditionally incremented and the result is checked
> against NTP_PHASE_LIMIT, but the increment itself can overflow,
> resulting in wrap-around to negative space.
>
> The user can supply some crazy values which is causing the overflow. Add
> an extra validation step checking that maxerror is reasonable.

The user can supply any value which can cause an overflow as the input
is unchecked. Add ...

Hmm?

> diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
> index b58dffc58a8f..321f251c02aa 100644
> --- a/kernel/time/timekeeping.c
> +++ b/kernel/time/timekeeping.c
> @@ -2388,6 +2388,11 @@ static int timekeeping_validate_timex(const struct __kernel_timex *txc)
>  		}
>  	}
>  
> +	if (txc->modes & ADJ_MAXERROR) {
> +		if (txc->maxerror < 0 || txc->maxerror > NTP_PHASE_LIMIT)
> +			return -EINVAL;
> +	}

I dug into history to find a Fixes tag. That unearthed something
interesting.  Exactly this check used to be there until commit
eea83d896e31 ("ntp: NTP4 user space bits update") which landed in
2.6.30. The change log says:

    "If some values for adjtimex() are outside the acceptable range, they
     are now simply normalized instead of letting the syscall fail."

The problem with that commit is that it did not do any normalization at
all and just relied on the actual time_maxerror handling in
second_overflow(), which is both insufficient and also prone to that
overflow issue.

So instead of turning the clock back, we might be better off to actually
put the normalization in place at the assignment:

    time_maxerror = min(max(0, txc->maxerror), NTP_PHASE_LIMIT);

or something like that.

Miroslav: Any opinion on that?

Thanks,

        tglx

Thomas Gleixner May 24, 2024, 12:44 p.m. UTC | #2

On Fri, May 24 2024 at 14:09, Thomas Gleixner wrote:
> On Fri, May 17 2024 at 20:22, Justin Stitt wrote:
> I dug into history to find a Fixes tag. That unearthed something
> interesting.  Exactly this check used to be there until commit
> eea83d896e31 ("ntp: NTP4 user space bits update") which landed in
> 2.6.30. The change log says:
>
>     "If some values for adjtimex() are outside the acceptable range, they
>      are now simply normalized instead of letting the syscall fail."
>
> The problem with that commit is that it did not do any normalization at
> all and just relied on the actual time_maxerror handling in
> second_overflow(), which is both insufficient and also prone to that
> overflow issue.
>
> So instead of turning the clock back, we might be better off to actually
> put the normalization in place at the assignment:
>
>     time_maxerror = min(max(0, txc->maxerror), NTP_PHASE_LIMIT);
>
> or something like that.

So that commit also removed the sanity check for time_esterror, but
that's not doing anything in the kernel other than being reset in
clear_ntp() and being handed back to user space. No idea what this is
actually used for.

Thanks,

        tglx

Justin Stitt May 24, 2024, 10:43 p.m. UTC | #3

Thomas,

I appreciate you reviewing my patches.

On Fri, May 24, 2024 at 5:09 AM Thomas Gleixner <[e-mail]> wrote:
>
> On Fri, May 17 2024 at 20:22, Justin Stitt wrote:
> > time_maxerror is unconditionally incremented and the result is checked
> > against NTP_PHASE_LIMIT, but the increment itself can overflow,
> > resulting in wrap-around to negative space.
> >
> > The user can supply some crazy values which is causing the overflow. Add
> > an extra validation step checking that maxerror is reasonable.
>
> The user can supply any value which can cause an overflow as the input
> is unchecked. Add ...
>
> Hmm?
>
> > diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
> > index b58dffc58a8f..321f251c02aa 100644
> > --- a/kernel/time/timekeeping.c
> > +++ b/kernel/time/timekeeping.c
> > @@ -2388,6 +2388,11 @@ static int timekeeping_validate_timex(const struct __kernel_timex *txc)
> >               }
> >       }
> >
> > +     if (txc->modes & ADJ_MAXERROR) {
> > +             if (txc->maxerror < 0 || txc->maxerror > NTP_PHASE_LIMIT)
> > +                     return -EINVAL;
> > +     }
>
> I dug into history to find a Fixes tag. That unearthed something
> interesting.  Exactly this check used to be there until commit
> eea83d896e31 ("ntp: NTP4 user space bits update") which landed in
> 2.6.30. The change log says:

Thanks for doing the archaeology.

>
>     "If some values for adjtimex() are outside the acceptable range, they
>      are now simply normalized instead of letting the syscall fail."
>
> The problem with that commit is that it did not do any normalization at
> all and just relied on the actual time_maxerror handling in
> second_overflow(), which is both insufficient and also prone to that
> overflow issue.
>
> So instead of turning the clock back, we might be better off to actually
> put the normalization in place at the assignment:
>
>     time_maxerror = min(max(0, txc->maxerror), NTP_PHASE_LIMIT);

A saturating resolution strategy is one that I've taken with some of
my other overflow patches.

... but how about: clamp(txc->maxerror, 0, NTP_PHASE_LIMIT)

>
> or something like that.
>
> Miroslav: Any opinion on that?
>
> Thanks,
>
>         tglx

Anyways, I'm waiting to see how the whole overflow/wraparound
discussion in general evolves and, of course, how the local discussion
about this patch shapes up.

Thanks
Justin

Thomas Gleixner May 24, 2024, 10:54 p.m. UTC | #4

Justin!

On Fri, May 24 2024 at 15:43, Justin Stitt wrote:
> I appreciate you reviewing my patches.

You're welcome!

> On Fri, May 24, 2024 at 5:09 AM Thomas Gleixner <[e-mail]> wrote:
>> So instead of turning the clock back, we might be better off to actually
>> put the normalization in place at the assignment:
>>
>>     time_maxerror = min(max(0, txc->maxerror), NTP_PHASE_LIMIT);
>
> A saturating resolution strategy is one that I've taken with some of
> my other overflow patches.
>
> ... but how about: clamp(txc->maxerror, 0, NTP_PHASE_LIMIT)

Duh. You are right, but that's too obvious :)

Thanks,

        tglx

Miroslav Lichvar May 27, 2024, 8:26 a.m. UTC | #5

On Fri, May 24, 2024 at 02:44:19PM +0200, Thomas Gleixner wrote:
> On Fri, May 24 2024 at 14:09, Thomas Gleixner wrote:
> > So instead of turning the clock back, we might be better off to actually
> > put the normalization in place at the assignment:
> >
> >     time_maxerror = min(max(0, txc->maxerror), NTP_PHASE_LIMIT);
> >
> > or something like that.

Yes, I think that's a better approach. Failing the system call could
break existing applications, e.g. ntpd can be configured to accept a
large root distance and it doesn't clamp the maxerror value, while
updating the PLL offset in the same adjtimex() call.

> So that commit also removed the sanity check for time_esterror, but
> that's not doing anything in the kernel other than being reset in
> clear_ntp() and being handed back to user space. No idea what this is
> actually used for.

It's a lower-bound estimate of the clock error, which applications can
check if it's acceptable for them. I think it should be clamped too.
It doesn't make much sense for it to be larger than the maximum error.

Another possible improvement of adjtimex() would be to set the UNSYNC
flag immediately in the call if maxerror >= 16s to avoid the delay of
up to 1 second for applications which check only that flag instead of
the maxerror value.

Thomas Gleixner May 29, 2024, 8:18 a.m. UTC | #6

On Mon, May 27 2024 at 10:26, Miroslav Lichvar wrote:
> On Fri, May 24, 2024 at 02:44:19PM +0200, Thomas Gleixner wrote:
>> On Fri, May 24 2024 at 14:09, Thomas Gleixner wrote:
>> > So instead of turning the clock back, we might be better off to actually
>> > put the normalization in place at the assignment:
>> >
>> >     time_maxerror = min(max(0, txc->maxerror), NTP_PHASE_LIMIT);
>> >
>> > or something like that.
>
> Yes, I think that's a better approach. Failing the system call could
> break existing applications, e.g. ntpd can be configured to accept a
> large root distance and it doesn't clamp the maxerror value, while
> updating the PLL offset in the same adjtimex() call.

Thanks for confirming. I suspected that, but the original change logs
are pretty useless in that regard.

>> So that commit also removed the sanity check for time_esterror, but
>> that's not doing anything in the kernel other than being reset in
>> clear_ntp() and being handed back to user space. No idea what this is
>> actually used for.
>
> It's a lower-bound estimate of the clock error, which applications can
> check if it's acceptable for them. I think it should be clamped too.
> It doesn't make much sense for it to be larger than the maximum error.

Ok.

> Another possible improvement of adjtimex() would be to set the UNSYNC
> flag immediately in the call if maxerror >= 16s to avoid the delay of
> up to 1 second for applications which check only that flag instead of
> the maxerror value.

That needs to be a seperate change.

Thanks,

        tglx

Patch

diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
index b58dffc58a8f..321f251c02aa 100644
--- a/kernel/time/timekeeping.c
+++ b/kernel/time/timekeeping.c
@@ -2388,6 +2388,11 @@  static int timekeeping_validate_timex(const struct __kernel_timex *txc)
 		}
 	}
 
+	if (txc->modes & ADJ_MAXERROR) {
+		if (txc->maxerror < 0 || txc->maxerror > NTP_PHASE_LIMIT)
+			return -EINVAL;
+	}
+
 	/*
 	 * Check for potential multiplication overflows that can
 	 * only happen on 64-bit systems: