In struct OptsVisitor, repeated_opts member points to a list in the
unprocessed_opts hash table after the list has been destroyed. A
subsequent call to visit_type_int() references the deleted list. It
results in use-after-free issue. Also, the Visitor object call back
functions are supposed to set the Error parameter in case of failure.

Signed-off-by: Andrey Shinkevich <andrey.shinkevich@virtuozzo.com>
---

The issue was detected after running tests/test-opts-visitor under the Valgrind tool:

 Invalid read of size 8
   at 0x55ADB95: g_queue_peek_head (in /usr/lib64/libglib-2.0.so.0.5600.1)
   by 0x12FD97: lookup_scalar (opts-visitor.c:310)
   by 0x13008A: opts_type_int64 (opts-visitor.c:395)
   by 0x1299C8: visit_type_int (qapi-visit-core.c:149)
   by 0x119389: test_opts_range_beyond (test-opts-visitor.c:240)

after
 Address 0x9563b30 is 0 bytes inside a block of size 24 free'd
   at 0x4C2ACBD: free (vg_replace_malloc.c:530)
   by 0x55A179D: g_free (in /usr/lib64/libglib-2.0.so.0.5600.1)
   by 0x55B92BF: g_slice_free1 (in /usr/lib64/libglib-2.0.so.0.5600.1)
   by 0x12F615: destroy_list (opts-visitor.c:102)
   by 0x558A859: ??? (in /usr/lib64/libglib-2.0.so.0.5600.1)
   by 0x12FC37: opts_next_list (opts-visitor.c:260)
   by 0x1296B1: visit_next_list (qapi-visit-core.c:88)
   by 0x119341: test_opts_range_beyond (test-opts-visitor.c:238)

 qapi/opts-visitor.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/qapi/opts-visitor.c b/qapi/opts-visitor.c
index 324b197..e95f766 100644
--- a/qapi/opts-visitor.c
+++ b/qapi/opts-visitor.c
@@ -228,6 +228,7 @@ opts_start_list(Visitor *v, const char *name, GenericList **list, size_t size,
         *list = g_malloc0(size);
     } else {
         *list = NULL;
+        error_setg(errp, QERR_MISSING_PARAMETER, name);
     }
 }
 
@@ -255,9 +256,14 @@ opts_next_list(Visitor *v, GenericList *tail, size_t size)
     case LM_IN_PROGRESS: {
         const QemuOpt *opt;
 
+        if (!ov->repeated_opts) {
+            return NULL;
+        }
+
         opt = g_queue_pop_head(ov->repeated_opts);
         if (g_queue_is_empty(ov->repeated_opts)) {
             g_hash_table_remove(ov->unprocessed_opts, opt->name);
+            ov->repeated_opts = NULL;
             return NULL;
         }
         break;
@@ -307,6 +313,10 @@ lookup_scalar(const OptsVisitor *ov, const char *name, Error **errp)
         return list ? g_queue_peek_tail(list) : NULL;
     }
     assert(ov->list_mode == LM_IN_PROGRESS);
+    if (!ov->repeated_opts) {
+        error_setg(errp, QERR_INVALID_PARAMETER, name);
+        return NULL;
+    }
     return g_queue_peek_head(ov->repeated_opts);
 }
 
-- 
1.8.3.1

Andrey Shinkevich <andrey.shinkevich@virtuozzo.com> writes:

> In struct OptsVisitor, repeated_opts member points to a list in the
> unprocessed_opts hash table after the list has been destroyed. A
> subsequent call to visit_type_int() references the deleted list. It
> results in use-after-free issue. Also, the Visitor object call back
> functions are supposed to set the Error parameter in case of failure.
>
> Signed-off-by: Andrey Shinkevich <andrey.shinkevich@virtuozzo.com>
> ---
>
> The issue was detected after running tests/test-opts-visitor under the Valgrind tool:
>
>  Invalid read of size 8
>    at 0x55ADB95: g_queue_peek_head (in /usr/lib64/libglib-2.0.so.0.5600.1)
>    by 0x12FD97: lookup_scalar (opts-visitor.c:310)
>    by 0x13008A: opts_type_int64 (opts-visitor.c:395)
>    by 0x1299C8: visit_type_int (qapi-visit-core.c:149)
>    by 0x119389: test_opts_range_beyond (test-opts-visitor.c:240)
>
> after
>  Address 0x9563b30 is 0 bytes inside a block of size 24 free'd
>    at 0x4C2ACBD: free (vg_replace_malloc.c:530)
>    by 0x55A179D: g_free (in /usr/lib64/libglib-2.0.so.0.5600.1)
>    by 0x55B92BF: g_slice_free1 (in /usr/lib64/libglib-2.0.so.0.5600.1)
>    by 0x12F615: destroy_list (opts-visitor.c:102)
>    by 0x558A859: ??? (in /usr/lib64/libglib-2.0.so.0.5600.1)
>    by 0x12FC37: opts_next_list (opts-visitor.c:260)
>    by 0x1296B1: visit_next_list (qapi-visit-core.c:88)
>    by 0x119341: test_opts_range_beyond (test-opts-visitor.c:238)

Reproduced.

>
>  qapi/opts-visitor.c | 10 ++++++++++
>  1 file changed, 10 insertions(+)
>
> diff --git a/qapi/opts-visitor.c b/qapi/opts-visitor.c
> index 324b197..e95f766 100644
> --- a/qapi/opts-visitor.c
> +++ b/qapi/opts-visitor.c
> @@ -228,6 +228,7 @@ opts_start_list(Visitor *v, const char *name, GenericList **list, size_t size,
       ov->repeated_opts = lookup_distinct(ov, name, errp);
       if (ov->repeated_opts) {
           ov->list_mode = LM_IN_PROGRESS;
>          *list = g_malloc0(size);
>      } else {
>          *list = NULL;
> +        error_setg(errp, QERR_MISSING_PARAMETER, name);

To get here, lookup_distinct() must have returned null.  It set an error
then.  Setting it again will crash.  Sure you tested this?

>      }
>  }
>  
> @@ -255,9 +256,14 @@ opts_next_list(Visitor *v, GenericList *tail, size_t size)
>      case LM_IN_PROGRESS: {
>          const QemuOpt *opt;
>  
> +        if (!ov->repeated_opts) {
> +            return NULL;
> +        }

How can ov->repeated_opts be null in state LM_IN_PROGRESS?

ov->repeated_opts is initially null (state LM_NONE).  It becomes
non-null on transition to state LM_IN_PROGRESS in opts_start_list(), and
null on transition back to LM_NONE in opts_end_list().

> +
>          opt = g_queue_pop_head(ov->repeated_opts);
>          if (g_queue_is_empty(ov->repeated_opts)) {
>              g_hash_table_remove(ov->unprocessed_opts, opt->name);
> +            ov->repeated_opts = NULL;
>              return NULL;
>          }

Uh, now you're violating the invariant I just described.  I suspect
that's how null can happen now.

If the fix should change the invariant, we need to review the entire
file to make sure nothing that relies on the invariant remains.  The
!ov->repeated_opts check above takes care of one case.  There may be
more.  Before we search for them, let's have a closer look at the bug
you found.  I'll do that below.

>          break;
> @@ -307,6 +313,10 @@ lookup_scalar(const OptsVisitor *ov, const char *name, Error **errp)
>          return list ? g_queue_peek_tail(list) : NULL;
>      }
>      assert(ov->list_mode == LM_IN_PROGRESS);
> +    if (!ov->repeated_opts) {
> +        error_setg(errp, QERR_INVALID_PARAMETER, name);
> +        return NULL;
> +    }

This is another case.

>      return g_queue_peek_head(ov->repeated_opts);
>  }

Now let's step back and review what valgrind is telling us.

The invalid read is indeed a use after free.

The free is opts_next_list()'s g_hash_table_remove(ov->unprocessed_opts,
opt->name), which in turn calls destroy_list() to destroy the value
associated with opt->name.

The use is lookup_scalar()'s g_queue_peek_head(ov->repeated_opts).
We're in state LM_IN_PROGRESS.  ov->repeated_opts points to a value
freed by opts_next_list().

Happens when test_opts_range_beyond() tries to visit more list elements
than actually present.

ov->repeated_opts becomes dangling when opts_next_list() destroys
ov->unprocessed_opts on reaching the end of the list.  Your patch zaps
it right after it becomes dangling.  Good.

But now the state machine has a new state "visiting beyond end of list":
list_mode == LM_IN_PROGRESS, repeated_opts == NULL.

Perhaps giving it its own ListMode member would be clearer.

Regardless, we need to convince ourselves that we handle the new state
correctly everywhere.  Have you done that?

On 01/08/2019 10:13, Markus Armbruster wrote:
> Andrey Shinkevich <andrey.shinkevich@virtuozzo.com> writes:
> 
>> In struct OptsVisitor, repeated_opts member points to a list in the
>> unprocessed_opts hash table after the list has been destroyed. A
>> subsequent call to visit_type_int() references the deleted list. It
>> results in use-after-free issue. Also, the Visitor object call back
>> functions are supposed to set the Error parameter in case of failure.
>>
>> Signed-off-by: Andrey Shinkevich <andrey.shinkevich@virtuozzo.com>
>> ---
>>
>> The issue was detected after running tests/test-opts-visitor under the Valgrind tool:
>>
>>   Invalid read of size 8
>>     at 0x55ADB95: g_queue_peek_head (in /usr/lib64/libglib-2.0.so.0.5600.1)
>>     by 0x12FD97: lookup_scalar (opts-visitor.c:310)
>>     by 0x13008A: opts_type_int64 (opts-visitor.c:395)
>>     by 0x1299C8: visit_type_int (qapi-visit-core.c:149)
>>     by 0x119389: test_opts_range_beyond (test-opts-visitor.c:240)
>>
>> after
>>   Address 0x9563b30 is 0 bytes inside a block of size 24 free'd
>>     at 0x4C2ACBD: free (vg_replace_malloc.c:530)
>>     by 0x55A179D: g_free (in /usr/lib64/libglib-2.0.so.0.5600.1)
>>     by 0x55B92BF: g_slice_free1 (in /usr/lib64/libglib-2.0.so.0.5600.1)
>>     by 0x12F615: destroy_list (opts-visitor.c:102)
>>     by 0x558A859: ??? (in /usr/lib64/libglib-2.0.so.0.5600.1)
>>     by 0x12FC37: opts_next_list (opts-visitor.c:260)
>>     by 0x1296B1: visit_next_list (qapi-visit-core.c:88)
>>     by 0x119341: test_opts_range_beyond (test-opts-visitor.c:238)
> 
> Reproduced.
> 
>>
>>   qapi/opts-visitor.c | 10 ++++++++++
>>   1 file changed, 10 insertions(+)
>>
>> diff --git a/qapi/opts-visitor.c b/qapi/opts-visitor.c
>> index 324b197..e95f766 100644
>> --- a/qapi/opts-visitor.c
>> +++ b/qapi/opts-visitor.c
>> @@ -228,6 +228,7 @@ opts_start_list(Visitor *v, const char *name, GenericList **list, size_t size,
>         ov->repeated_opts = lookup_distinct(ov, name, errp);
>         if (ov->repeated_opts) {
>             ov->list_mode = LM_IN_PROGRESS;
>>           *list = g_malloc0(size);
>>       } else {
>>           *list = NULL;
>> +        error_setg(errp, QERR_MISSING_PARAMETER, name);
> 
> To get here, lookup_distinct() must have returned null.  It set an error
> then.  Setting it again will crash.  Sure you tested this?
> 

Agreed, thank you. I will remove that redundant line in v2.

Andrey

>>       }
>>   }
>>   
>> @@ -255,9 +256,14 @@ opts_next_list(Visitor *v, GenericList *tail, size_t size)
>>       case LM_IN_PROGRESS: {
>>           const QemuOpt *opt;
>>   
>> +        if (!ov->repeated_opts) {
>> +            return NULL;
>> +        }
> 
> How can ov->repeated_opts be null in state LM_IN_PROGRESS?
> 
> ov->repeated_opts is initially null (state LM_NONE).  It becomes
> non-null on transition to state LM_IN_PROGRESS in opts_start_list(), and
> null on transition back to LM_NONE in opts_end_list().
> 
>> +
>>           opt = g_queue_pop_head(ov->repeated_opts);
>>           if (g_queue_is_empty(ov->repeated_opts)) {
>>               g_hash_table_remove(ov->unprocessed_opts, opt->name);
>> +            ov->repeated_opts = NULL;
>>               return NULL;
>>           }
> 
> Uh, now you're violating the invariant I just described.  I suspect
> that's how null can happen now.
> 
> If the fix should change the invariant, we need to review the entire
> file to make sure nothing that relies on the invariant remains.  The
> !ov->repeated_opts check above takes care of one case.  There may be
> more.  Before we search for them, let's have a closer look at the bug
> you found.  I'll do that below.
> 
>>           break;
>> @@ -307,6 +313,10 @@ lookup_scalar(const OptsVisitor *ov, const char *name, Error **errp)
>>           return list ? g_queue_peek_tail(list) : NULL;
>>       }
>>       assert(ov->list_mode == LM_IN_PROGRESS);
>> +    if (!ov->repeated_opts) {
>> +        error_setg(errp, QERR_INVALID_PARAMETER, name);
>> +        return NULL;
>> +    }
> 
> This is another case.
> 
>>       return g_queue_peek_head(ov->repeated_opts);
>>   }
> 
> Now let's step back and review what valgrind is telling us.
> 
> The invalid read is indeed a use after free.
> 
> The free is opts_next_list()'s g_hash_table_remove(ov->unprocessed_opts,
> opt->name), which in turn calls destroy_list() to destroy the value
> associated with opt->name.
> 
> The use is lookup_scalar()'s g_queue_peek_head(ov->repeated_opts).
> We're in state LM_IN_PROGRESS.  ov->repeated_opts points to a value
> freed by opts_next_list().
> 
> Happens when test_opts_range_beyond() tries to visit more list elements
> than actually present.
> 
> ov->repeated_opts becomes dangling when opts_next_list() destroys
> ov->unprocessed_opts on reaching the end of the list.  Your patch zaps
> it right after it becomes dangling.  Good.
> 
> But now the state machine has a new state "visiting beyond end of list":
> list_mode == LM_IN_PROGRESS, repeated_opts == NULL.
> 
> Perhaps giving it its own ListMode member would be clearer.
> 
> Regardless, we need to convince ourselves that we handle the new state
> correctly everywhere.  Have you done that?
> 

I have analyzed the code in qapi/opts-visitor.c and feel safer just 
assigning NULL to the dangling pointer ov->repeated_opts and can state 
that the unit tests and the iotests are passed. To keep the state 
clearer, as you suggested, I am going to declare a new mode LM_TRAVERSED 
in v2.

Andrey
-- 
With the best regards,
Andrey Shinkevich