[FFmpeg-devel,2/3] avcodec/lagarith: Optimize case with singleton probability distribution

Submitted by Michael Niedermayer on Dec. 24, 2018, 12:14 a.m.

Details

Message ID 20181224001451.8853-2-michael@niedermayer.cc
State Superseded
Headers show

Commit Message

Michael Niedermayer Dec. 24, 2018, 12:14 a.m.
Fixes: Timeout
Fixes: 10554/clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200

Found-by: continuous fuzzing process https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
 libavcodec/lagarith.c    | 36 ++++++++++++++++++++++++++++++++++++
 libavcodec/lagarithrac.h |  1 +
 2 files changed, 37 insertions(+)

Comments

Derek Buitenhuis Dec. 24, 2018, 4:40 p.m.
On 24/12/2018 00:14, Michael Niedermayer wrote:
> Fixes: Timeout
> Fixes: 10554/clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200
> 
> Found-by: continuous fuzzing processhttps://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
> Signed-off-by: Michael Niedermayer<michael@niedermayer.cc>
> ---
>   libavcodec/lagarith.c    | 36 ++++++++++++++++++++++++++++++++++++
>   libavcodec/lagarithrac.h |  1 +
>   2 files changed, 37 insertions(+)

This adds a load of completely uncommented and confusing code; it murders
readability for... what? Making a 'timeout' in a specific fuzzer go away?

Is there a real benefit or reason to pollute the code with this? Measurable and
useful speedup?

- Derek
Michael Niedermayer Dec. 24, 2018, 9:42 p.m.
On Mon, Dec 24, 2018 at 04:40:11PM +0000, Derek Buitenhuis wrote:
> On 24/12/2018 00:14, Michael Niedermayer wrote:
> > Fixes: Timeout
> > Fixes: 10554/clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200
> > 
> > Found-by: continuous fuzzing processhttps://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
> > Signed-off-by: Michael Niedermayer<michael@niedermayer.cc>
> > ---
> >   libavcodec/lagarith.c    | 36 ++++++++++++++++++++++++++++++++++++
> >   libavcodec/lagarithrac.h |  1 +
> >   2 files changed, 37 insertions(+)
> 
> This adds a load of completely uncommented and confusing code; it murders
> readability for... what? Making a 'timeout' in a specific fuzzer go away?
> 

> Is there a real benefit or reason to pollute the code with this? Measurable and
> useful speedup?

Yes, ive documented that more verbosly now below
i tend to be a bit terse by default on these fixes so as not to explain too detailedly
on how to abuse/exploit the code

commit 0ca7a8deeffd33e05ae15a447259b32b6678c727 (HEAD -> master)
Author: Michael Niedermayer <michael@niedermayer.cc>
Date:   Mon Dec 24 01:14:50 2018 +0100

    avcodec/lagarith: Optimize case with singleton probability distribution
    
    Fixes: Timeout
    Fixes: 10554/clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200
    
    In case of a Denial of Service attack, the attacker wants to maximize the load on the target
    per byte transmitted from the attacker.
    For such a DoS attack it is best for the attacker to setup the probabilities so that the
    arithmetic decoder does not advance in the bytestream that way the attacker only needs to
    transmit the initial bytes and header for an arbitrary large frame.
    This patch here optimizes this codepath and avoids executing the arithmetic decoder more than
    once. It thus reduces the load causes by this codepath on the target.
    We also could completely disallow this codepath but it appears such odd probability
    distributions are not invalid.
    
    Found-by: continuous fuzzing process https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
    Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>


[...]
Kieran Kunhya Dec. 24, 2018, 11:54 p.m.
>
> commit 0ca7a8deeffd33e05ae15a447259b32b6678c727 (HEAD -> master)
> Author: Michael Niedermayer <michael@niedermayer.cc>
> Date:   Mon Dec 24 01:14:50 2018 +0100
>
>     avcodec/lagarith: Optimize case with singleton probability distribution
>
>     Fixes: Timeout
>     Fixes:
> 10554/clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200
>
>     In case of a Denial of Service attack, the attacker wants to maximize
> the load on the target
>     per byte transmitted from the attacker.
>     For such a DoS attack it is best for the attacker to setup the
> probabilities so that the
>     arithmetic decoder does not advance in the bytestream that way the
> attacker only needs to
>     transmit the initial bytes and header for an arbitrary large frame.
>     This patch here optimizes this codepath and avoids executing the
> arithmetic decoder more than
>     once. It thus reduces the load causes by this codepath on the target.
>     We also could completely disallow this codepath but it appears such
> odd probability
>     distributions are not invalid.
>
>     Found-by: continuous fuzzing process
> https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
>     Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
>

This is a nonsense argument, a user could send a frame that was
99999999x99999999 in dimensions, would have the same effect.
The calling application should manage timeouts themselves in a sandbox or
container or similar.

Merry Xmas.

Kieran
Michael Niedermayer Dec. 25, 2018, 10:16 a.m.
On Mon, Dec 24, 2018 at 11:54:31PM +0000, Kieran Kunhya wrote:
> >
> > commit 0ca7a8deeffd33e05ae15a447259b32b6678c727 (HEAD -> master)
> > Author: Michael Niedermayer <michael@niedermayer.cc>
> > Date:   Mon Dec 24 01:14:50 2018 +0100
> >
> >     avcodec/lagarith: Optimize case with singleton probability distribution
> >
> >     Fixes: Timeout
> >     Fixes:
> > 10554/clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200
> >
> >     In case of a Denial of Service attack, the attacker wants to maximize
> > the load on the target
> >     per byte transmitted from the attacker.
> >     For such a DoS attack it is best for the attacker to setup the
> > probabilities so that the
> >     arithmetic decoder does not advance in the bytestream that way the
> > attacker only needs to
> >     transmit the initial bytes and header for an arbitrary large frame.
> >     This patch here optimizes this codepath and avoids executing the
> > arithmetic decoder more than
> >     once. It thus reduces the load causes by this codepath on the target.
> >     We also could completely disallow this codepath but it appears such
> > odd probability
> >     distributions are not invalid.
> >
> >     Found-by: continuous fuzzing process
> > https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
> >     Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> >
> 
> This is a nonsense argument, a user could send a frame that was
> 99999999x99999999 in dimensions, would have the same effect.

This suggested attack would not work, a user wanting to minimize these
DoS issues would have set AVCodecContext.max_pixels which would block this.


> The calling application should manage timeouts themselves in a sandbox or
> container or similar.

Its always possible and also a very good idea to have a 2nd line of defense
like a sandbox / VM, ... as you suggest here, I did and do agree here.
And also a 3rd line of defense, ...

But this doesnt mean we should not attempt to fix or mitigate 
security (or other) issues directly in the code.

I think the point you are raising has been raised previously, so let me
argue a little broader here and not specific to just what you suggest.

If you compare a native fix in the code with a fix by a timeout, a
fix by a timeout causes:
* The whole process to be killed, so any application using libavcodec
  would basically "crash" and would not neccessarily save its state,
  flush out buffers, write any trailers or do proper protocol shutdowns
  or save any unsafed data. This is a outcome that should be minimized
* Using a timeout as the main way to block DoS is difficult as there is
  often no good timeout value. Its not unexpected that a system may need to
  support processing large videos taking several hours, thats a long 
  time for a file of a hundread bytes in a DoS attack 
  100bytes from an attacker could cause the same load as 1000000000 bytes from
  a user.
* Worst maybe is that a tight timeout likely makes the system more vulnerable
  not less. because during an attack all the processes would likely slow
  down and real users would be pushed into the timeout even if the system
  without the user processes timeouting would still function correctly
  
Iam sure there are more arguments but above are the ones that came to my mind
ATM.

> 
> Merry Xmas.

Merry Xmas as well!

[...]
Paul B Mahol Dec. 25, 2018, 3:43 p.m.
On 12/25/18, Michael Niedermayer <michael@niedermayer.cc> wrote:
> On Mon, Dec 24, 2018 at 11:54:31PM +0000, Kieran Kunhya wrote:
>> >
>> > commit 0ca7a8deeffd33e05ae15a447259b32b6678c727 (HEAD -> master)
>> > Author: Michael Niedermayer <michael@niedermayer.cc>
>> > Date:   Mon Dec 24 01:14:50 2018 +0100
>> >
>> >     avcodec/lagarith: Optimize case with singleton probability
>> > distribution
>> >
>> >     Fixes: Timeout
>> >     Fixes:
>> > 10554/clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200
>> >
>> >     In case of a Denial of Service attack, the attacker wants to
>> > maximize
>> > the load on the target
>> >     per byte transmitted from the attacker.
>> >     For such a DoS attack it is best for the attacker to setup the
>> > probabilities so that the
>> >     arithmetic decoder does not advance in the bytestream that way the
>> > attacker only needs to
>> >     transmit the initial bytes and header for an arbitrary large frame.
>> >     This patch here optimizes this codepath and avoids executing the
>> > arithmetic decoder more than
>> >     once. It thus reduces the load causes by this codepath on the
>> > target.
>> >     We also could completely disallow this codepath but it appears such
>> > odd probability
>> >     distributions are not invalid.
>> >
>> >     Found-by: continuous fuzzing process
>> > https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
>> >     Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
>> >
>>
>> This is a nonsense argument, a user could send a frame that was
>> 99999999x99999999 in dimensions, would have the same effect.
>
> This suggested attack would not work, a user wanting to minimize these
> DoS issues would have set AVCodecContext.max_pixels which would block this.
>
>
>> The calling application should manage timeouts themselves in a sandbox or
>> container or similar.
>
> Its always possible and also a very good idea to have a 2nd line of defense
> like a sandbox / VM, ... as you suggest here, I did and do agree here.
> And also a 3rd line of defense, ...
>
> But this doesnt mean we should not attempt to fix or mitigate
> security (or other) issues directly in the code.
>
> I think the point you are raising has been raised previously, so let me
> argue a little broader here and not specific to just what you suggest.
>
> If you compare a native fix in the code with a fix by a timeout, a
> fix by a timeout causes:
> * The whole process to be killed, so any application using libavcodec
>   would basically "crash" and would not neccessarily save its state,
>   flush out buffers, write any trailers or do proper protocol shutdowns
>   or save any unsafed data. This is a outcome that should be minimized
> * Using a timeout as the main way to block DoS is difficult as there is
>   often no good timeout value. Its not unexpected that a system may need to
>   support processing large videos taking several hours, thats a long
>   time for a file of a hundread bytes in a DoS attack
>   100bytes from an attacker could cause the same load as 1000000000 bytes
> from
>   a user.
> * Worst maybe is that a tight timeout likely makes the system more
> vulnerable
>   not less. because during an attack all the processes would likely slow
>   down and real users would be pushed into the timeout even if the system
>   without the user processes timeouting would still function correctly
>
> Iam sure there are more arguments but above are the ones that came to my
> mind
> ATM.
>
>>
>> Merry Xmas.
>
> Merry Xmas as well!
>
> [...]
> --
> Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
>
> Those who would give up essential Liberty, to purchase a little
> temporary Safety, deserve neither Liberty nor Safety -- Benjamin Franklin
>

This is still missing numbers/statistics.
Paul B Mahol Dec. 25, 2018, 3:45 p.m.
On 12/25/18, Paul B Mahol <onemda@gmail.com> wrote:
> On 12/25/18, Michael Niedermayer <michael@niedermayer.cc> wrote:
>> On Mon, Dec 24, 2018 at 11:54:31PM +0000, Kieran Kunhya wrote:
>>> >
>>> > commit 0ca7a8deeffd33e05ae15a447259b32b6678c727 (HEAD -> master)
>>> > Author: Michael Niedermayer <michael@niedermayer.cc>
>>> > Date:   Mon Dec 24 01:14:50 2018 +0100
>>> >
>>> >     avcodec/lagarith: Optimize case with singleton probability
>>> > distribution
>>> >
>>> >     Fixes: Timeout
>>> >     Fixes:
>>> > 10554/clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200
>>> >
>>> >     In case of a Denial of Service attack, the attacker wants to
>>> > maximize
>>> > the load on the target
>>> >     per byte transmitted from the attacker.
>>> >     For such a DoS attack it is best for the attacker to setup the
>>> > probabilities so that the
>>> >     arithmetic decoder does not advance in the bytestream that way the
>>> > attacker only needs to
>>> >     transmit the initial bytes and header for an arbitrary large
>>> > frame.
>>> >     This patch here optimizes this codepath and avoids executing the
>>> > arithmetic decoder more than
>>> >     once. It thus reduces the load causes by this codepath on the
>>> > target.
>>> >     We also could completely disallow this codepath but it appears
>>> > such
>>> > odd probability
>>> >     distributions are not invalid.
>>> >
>>> >     Found-by: continuous fuzzing process
>>> > https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
>>> >     Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
>>> >
>>>
>>> This is a nonsense argument, a user could send a frame that was
>>> 99999999x99999999 in dimensions, would have the same effect.
>>
>> This suggested attack would not work, a user wanting to minimize these
>> DoS issues would have set AVCodecContext.max_pixels which would block
>> this.
>>
>>
>>> The calling application should manage timeouts themselves in a sandbox
>>> or
>>> container or similar.
>>
>> Its always possible and also a very good idea to have a 2nd line of
>> defense
>> like a sandbox / VM, ... as you suggest here, I did and do agree here.
>> And also a 3rd line of defense, ...
>>
>> But this doesnt mean we should not attempt to fix or mitigate
>> security (or other) issues directly in the code.
>>
>> I think the point you are raising has been raised previously, so let me
>> argue a little broader here and not specific to just what you suggest.
>>
>> If you compare a native fix in the code with a fix by a timeout, a
>> fix by a timeout causes:
>> * The whole process to be killed, so any application using libavcodec
>>   would basically "crash" and would not neccessarily save its state,
>>   flush out buffers, write any trailers or do proper protocol shutdowns
>>   or save any unsafed data. This is a outcome that should be minimized
>> * Using a timeout as the main way to block DoS is difficult as there is
>>   often no good timeout value. Its not unexpected that a system may need
>> to
>>   support processing large videos taking several hours, thats a long
>>   time for a file of a hundread bytes in a DoS attack
>>   100bytes from an attacker could cause the same load as 1000000000 bytes
>> from
>>   a user.
>> * Worst maybe is that a tight timeout likely makes the system more
>> vulnerable
>>   not less. because during an attack all the processes would likely slow
>>   down and real users would be pushed into the timeout even if the system
>>   without the user processes timeouting would still function correctly
>>
>> Iam sure there are more arguments but above are the ones that came to my
>> mind
>> ATM.
>>
>>>
>>> Merry Xmas.
>>
>> Merry Xmas as well!
>>
>> [...]
>> --
>> Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
>>
>> Those who would give up essential Liberty, to purchase a little
>> temporary Safety, deserve neither Liberty nor Safety -- Benjamin Franklin
>>
>
> This is still missing numbers/statistics.
>

And comments explaining added code.
Michael Niedermayer Dec. 26, 2018, 11:18 a.m.
On Tue, Dec 25, 2018 at 04:43:24PM +0100, Paul B Mahol wrote:
> On 12/25/18, Michael Niedermayer <michael@niedermayer.cc> wrote:
> > On Mon, Dec 24, 2018 at 11:54:31PM +0000, Kieran Kunhya wrote:
> >> >
> >> > commit 0ca7a8deeffd33e05ae15a447259b32b6678c727 (HEAD -> master)
> >> > Author: Michael Niedermayer <michael@niedermayer.cc>
> >> > Date:   Mon Dec 24 01:14:50 2018 +0100
> >> >
> >> >     avcodec/lagarith: Optimize case with singleton probability
> >> > distribution
> >> >
> >> >     Fixes: Timeout
> >> >     Fixes:
> >> > 10554/clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200
> >> >
> >> >     In case of a Denial of Service attack, the attacker wants to
> >> > maximize
> >> > the load on the target
> >> >     per byte transmitted from the attacker.
> >> >     For such a DoS attack it is best for the attacker to setup the
> >> > probabilities so that the
> >> >     arithmetic decoder does not advance in the bytestream that way the
> >> > attacker only needs to
> >> >     transmit the initial bytes and header for an arbitrary large frame.
> >> >     This patch here optimizes this codepath and avoids executing the
> >> > arithmetic decoder more than
> >> >     once. It thus reduces the load causes by this codepath on the
> >> > target.
> >> >     We also could completely disallow this codepath but it appears such
> >> > odd probability
> >> >     distributions are not invalid.
> >> >
> >> >     Found-by: continuous fuzzing process
> >> > https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
> >> >     Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> >> >
> >>
> >> This is a nonsense argument, a user could send a frame that was
> >> 99999999x99999999 in dimensions, would have the same effect.
> >
> > This suggested attack would not work, a user wanting to minimize these
> > DoS issues would have set AVCodecContext.max_pixels which would block this.
> >
> >
> >> The calling application should manage timeouts themselves in a sandbox or
> >> container or similar.
> >
> > Its always possible and also a very good idea to have a 2nd line of defense
> > like a sandbox / VM, ... as you suggest here, I did and do agree here.
> > And also a 3rd line of defense, ...
> >
> > But this doesnt mean we should not attempt to fix or mitigate
> > security (or other) issues directly in the code.
> >
> > I think the point you are raising has been raised previously, so let me
> > argue a little broader here and not specific to just what you suggest.
> >
> > If you compare a native fix in the code with a fix by a timeout, a
> > fix by a timeout causes:
> > * The whole process to be killed, so any application using libavcodec
> >   would basically "crash" and would not neccessarily save its state,
> >   flush out buffers, write any trailers or do proper protocol shutdowns
> >   or save any unsafed data. This is a outcome that should be minimized
> > * Using a timeout as the main way to block DoS is difficult as there is
> >   often no good timeout value. Its not unexpected that a system may need to
> >   support processing large videos taking several hours, thats a long
> >   time for a file of a hundread bytes in a DoS attack
> >   100bytes from an attacker could cause the same load as 1000000000 bytes
> > from
> >   a user.
> > * Worst maybe is that a tight timeout likely makes the system more
> > vulnerable
> >   not less. because during an attack all the processes would likely slow
> >   down and real users would be pushed into the timeout even if the system
> >   without the user processes timeouting would still function correctly
> >
> > Iam sure there are more arguments but above are the ones that came to my
> > mind
> > ATM.
> >
> >>
> >> Merry Xmas.
> >
> > Merry Xmas as well!
> >
> > [...]
> > --
> > Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
> >
> > Those who would give up essential Liberty, to purchase a little
> > temporary Safety, deserve neither Liberty nor Safety -- Benjamin Franklin
> >
> 
> This is still missing numbers/statistics.

Before: Executed clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200 in 27400 ms
After:  Executed clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200 in 6676 ms

(will add this to the commit message)


[...]

Patch hide | download patch | download mbox

diff --git a/libavcodec/lagarith.c b/libavcodec/lagarith.c
index 59169be5de..0b222e1acd 100644
--- a/libavcodec/lagarith.c
+++ b/libavcodec/lagarith.c
@@ -175,6 +175,7 @@  static int lag_read_prob_header(lag_rac *rac, GetBitContext *gb)
     if (nnz == 1 && (show_bits_long(gb, 32) & 0xFFFFFF)) {
         return AVERROR_INVALIDDATA;
     }
+    rac->nnz = nnz;
 
     /* Scale probabilities so cumulative probability is an even power of 2. */
     scale_factor = av_log2(cumul_prob);
@@ -332,6 +333,41 @@  static int lag_decode_line(LagarithContext *l, lag_rac *rac,
     if (!esc_count)
         esc_count = -1;
 
+    if (rac->nnz == 1) {
+        int v = -1;;
+handle_zeros1:
+        if (l->zeros_rem) {
+            int count = FFMIN(l->zeros_rem, width - i);
+            memset(dst + i, 0, count);
+            i += count;
+            l->zeros_rem -= count;
+        }
+
+        while (i < width) {
+            if (v < 0)
+                v =  lag_get_rac(rac);
+
+            dst[i] =v;
+            ret++;
+
+            if (v)
+                l->zeros = 0;
+            else
+                l->zeros++;
+
+            i++;
+            if (l->zeros == esc_count) {
+                ret++;
+
+                l->zeros = 0;
+
+                l->zeros_rem = lag_calc_zero_run(v);
+                goto handle_zeros1;
+            }
+        }
+        return ret;
+    }
+
     /* Output any zeros remaining from the previous run */
 handle_zeros:
     if (l->zeros_rem) {
diff --git a/libavcodec/lagarithrac.h b/libavcodec/lagarithrac.h
index ee836d01db..9f37f3939c 100644
--- a/libavcodec/lagarithrac.h
+++ b/libavcodec/lagarithrac.h
@@ -47,6 +47,7 @@  typedef struct lag_rac {
     const uint8_t *bytestream;        /**< Current position in input bytestream. */
     const uint8_t *bytestream_end;    /**< End position of input bytestream. */
 
+    int nnz;
     int overread;
 #define MAX_OVERREAD 4