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

Submitted by Michael Niedermayer on Jan. 15, 2019, 11:38 p.m.

Details

Message ID 20190115233853.9711-1-michael@niedermayer.cc
State New
Headers show

Commit Message

Michael Niedermayer Jan. 15, 2019, 11:38 p.m.
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.

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

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    | 39 +++++++++++++++++++++++++++++++++++++++
 libavcodec/lagarithrac.h |  1 +
 2 files changed, 40 insertions(+)

Patch hide | download patch | download mbox

diff --git a/libavcodec/lagarith.c b/libavcodec/lagarith.c
index 59169be5de..0dd9717266 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,44 @@  static int lag_decode_line(LagarithContext *l, lag_rac *rac,
     if (!esc_count)
         esc_count = -1;
 
+    // Detect a odd corner case which consumes disproportional computational
+    // resources in relation to the input size. We optimize this worst case
+    // to reduce its impact.
+    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