[Xen-changelog] [xen master] lzo: check for length overrun in variable length encoding

[patchbot@xxxxxxx]

commit 10a94ddbd2eb97365872cd14be93837c4613e09d
Author:     Willy Tarreau <w@xxxxxx>
AuthorDate: Tue Nov 4 13:09:09 2014 +0100
Commit:     Jan Beulich <jbeulich@xxxxxxxx>
CommitDate: Tue Nov 4 13:11:06 2014 +0100

    lzo: check for length overrun in variable length encoding
    
    This fix ensures that we never meet an integer overflow while adding
    255 while parsing a variable length encoding. It works differently from
    commit 504f70b6 ("lzo: properly check for overruns") because instead of
    ensuring that we don't overrun the input, which is tricky to guarantee
    due to many assumptions in the code, it simply checks that the cumulated
    number of 255 read cannot overflow by bounding this number.
    
    The MAX_255_COUNT is the maximum number of times we can add 255 to a base
    count without overflowing an integer. The multiply will overflow when
    multiplying 255 by more than MAXINT/255. The sum will overflow earlier
    depending on the base count. Since the base count is taken from a u8
    and a few bits, it is safe to assume that it will always be lower than
    or equal to 2*255, thus we can always prevent any overflow by accepting
    two less 255 steps.
    
    This patch also reduces the CPU overhead and actually increases performance
    by 1.1% compared to the initial code, while the previous fix costs 3.1%
    (measured on x86_64).
    
    The fix needs to be backported to all currently supported stable kernels.
    
    Reported-by: Willem Pinckaers <willem@xxxxxxxxxxxxxx>
    Signed-off-by: Willy Tarreau <w@xxxxxx>
    [original Linux commit: 72cf9012]
    Signed-off-by: Jan Beulich <jbeulich@xxxxxxxx>
    Acked-by: Ian Campbell <ian.campbell@xxxxxxxxxx>
---
 xen/common/lzo.c |   43 +++++++++++++++++++++++++++++++++++++------
 1 files changed, 37 insertions(+), 6 deletions(-)

diff --git a/xen/common/lzo.c b/xen/common/lzo.c
index 7338aee..74831cb 100644
--- a/xen/common/lzo.c
+++ b/xen/common/lzo.c
@@ -381,6 +381,16 @@ int lzo1x_1_compress(const unsigned char *in, size_t 
in_len,
 #define NEED_OP(x)     if (!HAVE_OP(x)) goto output_overrun
 #define TEST_LB(m_pos) if ((m_pos) < out) goto lookbehind_overrun
 
+/* This MAX_255_COUNT is the maximum number of times we can add 255 to a base
+ * count without overflowing an integer. The multiply will overflow when
+ * multiplying 255 by more than MAXINT/255. The sum will overflow earlier
+ * depending on the base count. Since the base count is taken from a u8
+ * and a few bits, it is safe to assume that it will always be lower than
+ * or equal to 2*255, thus we can always prevent any overflow by accepting
+ * two less 255 steps. See Documentation/lzo.txt for more information.
+ */
+#define MAX_255_COUNT      ((((size_t)~0) / 255) - 2)
+
 int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
                           unsigned char *out, size_t *out_len)
 {
@@ -411,12 +421,19 @@ int lzo1x_decompress_safe(const unsigned char *in, size_t 
in_len,
         if (t < 16) {
             if (likely(state == 0)) {
                 if (unlikely(t == 0)) {
+                    size_t offset;
+                    const unsigned char *ip_last = ip;
+
                     while (unlikely(*ip == 0)) {
-                        t += 255;
                         ip++;
                         NEED_IP(1);
                     }
-                    t += 15 + *ip++;
+                    offset = ip - ip_last;
+                    if (unlikely(offset > MAX_255_COUNT))
+                        return LZO_E_ERROR;
+
+                    offset = (offset << 8) - offset;
+                    t += offset + 15 + *ip++;
                 }
                 t += 3;
  copy_literal_run:
@@ -472,12 +489,19 @@ int lzo1x_decompress_safe(const unsigned char *in, size_t 
in_len,
         } else if (t >= 32) {
             t = (t & 31) + (3 - 1);
             if (unlikely(t == 2)) {
+                size_t offset;
+                const unsigned char *ip_last = ip;
+
                 while (unlikely(*ip == 0)) {
-                    t += 255;
                     ip++;
                     NEED_IP(1);
                 }
-                t += 31 + *ip++;
+                offset = ip - ip_last;
+                if (unlikely(offset > MAX_255_COUNT))
+                    return LZO_E_ERROR;
+
+                offset = (offset << 8) - offset;
+                t += offset + 31 + *ip++;
                 NEED_IP(2);
             }
             m_pos = op - 1;
@@ -490,12 +514,19 @@ int lzo1x_decompress_safe(const unsigned char *in, size_t 
in_len,
             m_pos -= (t & 8) << 11;
             t = (t & 7) + (3 - 1);
             if (unlikely(t == 2)) {
+                size_t offset;
+                const unsigned char *ip_last = ip;
+
                 while (unlikely(*ip == 0)) {
-                    t += 255;
                     ip++;
                     NEED_IP(1);
                 }
-                t += 7 + *ip++;
+                offset = ip - ip_last;
+                if (unlikely(offset > MAX_255_COUNT))
+                    return LZO_E_ERROR;
+
+                offset = (offset << 8) - offset;
+                t += offset + 7 + *ip++;
                 NEED_IP(2);
             }
             next = get_unaligned_le16(ip);
--
generated by git-patchbot for /home/xen/git/xen.git#master

_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxx
http://lists.xensource.com/xen-changelog