Project

General

Profile

Actions

Feature #8234

closed

Error traces comparison for races

Added by Pavel Andrianov almost 7 years ago. Updated over 6 years ago.

Status:
Closed
Priority:
Urgent
Category:
Bridge
Target version:
Start date:
06/05/2017
Due date:
09/23/2017
% Done:

100%

Estimated time:
Published in build:

Description

Now, the comparison of race traces is not good enough if traces (precisely, sources) have no model functions (just notes and warnings). The calltree option does not compare at all, callstack option considers only one trace (from pair). The best idea is to consider notes as model functions and use them in trace comparison algorithm. May be, it should be implemented as special option.


Files

report_struct_world_tmslist.zip (12.3 MB) report_struct_world_tmslist.zip Pavel Andrianov, 06/05/2017 04:21 PM
witness.struct_at76_priv__auth_mode.graphml (1.61 MB) witness.struct_at76_priv__auth_mode.graphml Pavel Andrianov, 06/15/2017 04:19 PM
error-trace(1).json (2.66 MB) error-trace(1).json Pavel Andrianov, 07/25/2017 06:56 PM

Related issues 1 (0 open1 closed)

Blocked by Klever - Feature #8240: Fix transformation of witnesses to error traces for multithreaded softwareClosedIlja Zakharov06/13/2017

Actions
Actions #1

Updated by Vadim Mutilin almost 7 years ago

The issue is of high priority

Actions #2

Updated by Evgeny Novikov almost 7 years ago

  • Status changed from New to Feedback
  • Priority changed from Normal to Immediate

This is a bug that should be fixed ASAP independently on features that are implemented at the moment.

But you need to attach an example of such the error trace and likely referred sources.

Actions #3

Updated by Pavel Andrianov almost 7 years ago

Attach an unsafe report with one error trace

Actions #4

Updated by Pavel Andrianov almost 7 years ago

  • Priority changed from Normal to Immediate

Status and priority are changed accidentally

Actions #5

Updated by Evgeny Novikov almost 7 years ago

  • Tracker changed from Feature to Bug
  • Detected in build set to svn
Actions #6

Updated by Vladimir Gratinskiy almost 7 years ago

  • Tracker changed from Bug to Feature

Where did you find a bug?

1) "call_stack" function. Did you see the description? Here it is:
This function is extracting the error trace call stack to first warning.
Return list of lists of function names in json format.

As you can see even in description I consider that only one warning is used for this function.

2) "call_stack_tree" function. It's description:

This function is extracting the error trace call stack tree.
All its leaves are model functions.
Return list of lists of levels of function names in json format.

Warnings are "red notes" only, not a functions.

3) "call_forests" and "forests_callbacks" are for error traces with callback actions only.

So I need to implement new FEATURE - new function like "call_stack", but which counts all warnings.

Actions #7

Updated by Vladimir Gratinskiy almost 7 years ago

  • Due date set to 06/07/2017
  • Status changed from Open to Resolved
  • % Done changed from 0 to 100

Implemented new function "call_stack_all_warnings" in branch "feature_8234".
You need "Population" for existing database.

Actions #8

Updated by Pavel Andrianov almost 7 years ago

  • Status changed from Resolved to Open

I tried the new feature and noticed that now all comparison algorithms are broken. If the previous version of callstack (origin callstack, without all traces) produced a mark, which was applied to the three traces, now the same mark, with the same conversion and comparison functions applies to the all 800 unsafes in all launches. The same result is with other algorithms, like callstack_all_warnings, a new mark is applied to all unsafes even the extracted callstacks are not empty.
One more comment, I suggested to implement an algorithm similar to calltree comparison: consider notes as model functions and use them in the comparison algorithm. Is it possible?

Actions #9

Updated by Pavel Andrianov almost 7 years ago

I found an exception from bridge, may be it is helpful.

Error traces comparison failed: division by zero
Traceback (most recent call last):
  File "/home/alpha/git/klever/bridge/marks/UnsafeUtils.py", line 359, in __connect
    compare = CompareTrace(self._functions[mark_id], self._patterns[mark_id], unsafe)
  File "/home/alpha/git/klever/bridge/marks/CompareTrace.py", line 64, in __init__
    self.result = func()
  File "/home/alpha/git/klever/bridge/marks/CompareTrace.py", line 139, in callstack_all_warnings_compare
    return len(converted_set & pattern_set)/len(err_trace_converted)
ZeroDivisionError: division by zero
Actions #10

Updated by Vladimir Gratinskiy almost 7 years ago

  • Status changed from Open to Resolved

Pavel Andrianov wrote:

I tried the new feature and noticed that now all comparison algorithms are broken. If the previous version of callstack (origin callstack, without all traces) produced a mark, which was applied to the three traces, now the same mark, with the same conversion and comparison functions applies to the all 800 unsafes in all launches. The same result is with other algorithms, like callstack_all_warnings, a new mark is applied to all unsafes even the extracted callstacks are not empty.

I don't know why this could happen for you. If it is possible then recreate the database. If not, then do in pycharm console:
from marks.models import ErrorTraceConvertionCache
ErrorTraceConvertionCache.objects.all().delete()

Anyway you have to restart Bridge after you changed to this branch.

One more comment, I suggested to implement an algorithm similar to calltree comparison: consider notes as model functions and use them in the comparison algorithm. Is it possible?

I've implemented new functions. You should choose comparison function the same as convert. So for "call_stack_all_warnings" only "callstack_all_warnings_compare" would work correctly and for "calltree_all_warnings" choose only "calltree_warnings_compare".

The bug with division by zero is fixed.

Actions #11

Updated by Pavel Andrianov almost 7 years ago

  • Status changed from Resolved to Open

I have cleaned the cache, restart the Bridge several times, anyway a mark applies to all unsafes independently from the comparison algorithm. I can share the database dump and media/ directory, could you reproduce the bug with my data on your machine?

calltree_all_warnings algorithm extracts only one calltree (not a pair to both of warnings). Is it bug or feature?

Actions #12

Updated by Vladimir Gratinskiy almost 7 years ago

When you connect one error trace like:
f1 { f2 { warning1
to another like
f3 { f4 { warning2
you get error trace:
f1 { f2 { warning1; f3 { f4 { warning2;

so the converted error trace will be:
[ ["f1", "f2", "warning1 f3", "f4", "warning"] ]

So the problem is with error trace - you should return from all entered functions in first error trace before connecting the second one.

For example, this error trace:
f1 { f2 { warning1; } } f3 { f4 { warning2;
will produce this converted trace:
[ ["f1", "f2", "warning1"], ["f3", "f4", "warning2"] ]

Actions #13

Updated by Evgeny Novikov almost 7 years ago

  • Priority changed from Immediate to High
After all we decided to:
  1. Output more proper witnesses for multithreaded software. Pavel will do it in CPALocator.
  2. Fix transformation of witnesses to error traces. Ilja or I will do that.
  3. And just after that return back to this feature request.

Eventually nice error traces are expected to be shown in all cases.

Actions #14

Updated by Pavel Andrianov almost 7 years ago

Attach an example a new witness output. There is a branching note (id = 1894), where a thread is created. Now, etv fails dumping converted trace to json. Likely, it expects sequential trace, not branching one.

Actions #15

Updated by Evgeny Novikov almost 7 years ago

  • Priority changed from High to Urgent

Users need data dace marks.

Actions #16

Updated by Pavel Andrianov over 6 years ago

Are there any news? I tried new witness visualization branch with different comparison algorithms. Most of them produce empty converted error trace or extract a trace only from one thread.

Actions #17

Updated by Pavel Andrianov over 6 years ago

An example of error trace attached.

Converted error trace is expected to be similar to callback_forest algorithm. Converted error trace is a set of converted threads. Converted thread is a sequence of particular edges of the same threadId. Particular edges are: edges with 'note' attribute, edges with 'warning' attribute and all function entries (callstacks) to them. Two converted traces are equal if they are equal as sets of their converted threads (not as lists!).

Actions #18

Updated by Vladimir Gratinskiy over 6 years ago

  • Due date changed from 06/07/2017 to 07/26/2017
  • Status changed from Open to Resolved

New functions are implemented in branch "feature_8234" - all_forests() and all_forests_compare(). Convertion creates list. Each element of it is list of forests in the same thread. Forest is tree of notes, warnings and functions with it. But in compare the set of these lists will be compared. Example:

THREAD_1
f1() {
  note1
  f2() {
    warn1
  }
}
THREAD_2
f3() {
  note2
  (note3)f4() {
  }
}
f5() {
  f6() {
    warn2
  }
}
f7() {
}

The converted trace will be:
[
  [{f1: [{note1: []}, {f2: [{warn1: []}]}]}],
  [{f3: [{note2: []}, {f4: []}]}, {f5: [{f6: [{warn2: []}]}]}]
]

Comparison function will compare this set of strings:
{
  "[{f1: [{note1: []}, {f2: [{warn1: []}]}]}]",
  "[{f3: [{note2: []}, {f4: []}]}, {f5: [{f6: [{warn2: []}]}]}]"
}

Actions #19

Updated by Pavel Andrianov over 6 years ago

  • Status changed from Resolved to Verified

Quick check of several generated marks with new comparison function shows no problems.

Actions #20

Updated by Pavel Andrianov over 6 years ago

Just a comment. A text of 'warning' preserves association of marks within one job ('warning' is unique). For experiment I disabled the text description in converting function, so, different traces can be associated with one mark. May be, we need other description tag, which has information not for human (as 'warning') but for comparison of traces, because we can not totally reject the warning edge itself.

Actions #21

Updated by Pavel Andrianov over 6 years ago

A question. In all my reports I have three threads: thread0 creates thread1 and thread2, thread1 and thread2 have path to a warning without any other thread creations. Converted traces have only thread1 and thread2. Is it feature, that thread0 is not included into converted error trace? Seems, that it is useful, because I do not want similarity 33% for all reports (thread0 is common for every one).

Actions #22

Updated by Vladimir Gratinskiy over 6 years ago

Pavel Andrianov wrote:

A question. In all my reports I have three threads: thread0 creates thread1 and thread2, thread1 and thread2 have path to a warning without any other thread creations. Converted traces have only thread1 and thread2. Is it feature, that thread0 is not included into converted error trace? Seems, that it is useful, because I do not want similarity 33% for all reports (thread0 is common for every one).

What do you want to have in thread0? I suppose it doesn't contain any functions.

Actions #23

Updated by Pavel Andrianov over 6 years ago

Vladimir Gratinskiy wrote:

What do you want to have in thread0? I suppose it doesn't contain any functions.

Nothing special. It was just a question: absence of empty thread0 - is a bug or a feature? Do you skip all empty threads?

Actions #24

Updated by Vladimir Gratinskiy over 6 years ago

Pavel Andrianov wrote:

Vladimir Gratinskiy wrote:

What do you want to have in thread0? I suppose it doesn't contain any functions.

Nothing special. It was just a question: absence of empty thread0 - is a bug or a feature? Do you skip all empty threads?

Yes, I skip all empty threads.

Actions #25

Updated by Evgeny Novikov over 6 years ago

  • Target version set to 0.2
Actions #26

Updated by Evgeny Novikov over 6 years ago

  • Status changed from Verified to Open

Please, merge the latest master to this branch since Git doesn't provide this for free.

Actions #27

Updated by Vladimir Gratinskiy over 6 years ago

  • Status changed from Open to Resolved

The master was merged. I've also removed all error trace covert and comparison functions that are not used now and updated descriptions. You need to populate DB to update list of functions on server. This action will remove all marks that had removed functions. In addition I've changed comparison functions and now it calculate Jaccard index. You need to update "Unsafe marks cache" on manager page for all existing jobs. It will be long.

Actions #28

Updated by Evgeny Novikov over 6 years ago

  • Status changed from Resolved to Open

We have been actively discussing everything related with error trace converting and comparing in frames of this issue. Now it looks that we are approaching the end.

Actions #29

Updated by Vladimir Gratinskiy over 6 years ago

  • Due date changed from 07/26/2017 to 09/23/2017
  • Status changed from Open to Resolved

The function is changed (branch feature_8234). See examples and new descriptions in https://docs.google.com/document/d/18utoqx1UfpEgE8Npf4Ope8B49frN7Zy0XaMELtLxZb8/edit.

Actions #30

Updated by Evgeny Novikov over 6 years ago

  • Status changed from Resolved to Open

I observed the following issue when migrating my local database:

Running migrations:
  Applying marks.0016_change_funcs... OK
  Applying marks.0017_markunsafecompare_convert... OK
  Applying marks.0018_set_convert... OK
  Applying marks.0019_auto_20170919_1517...Traceback (most recent call last):
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/backends/utils.py", line 65, in execute
    return self.cursor.execute(sql, params)
psycopg2.IntegrityError: ОШИБКА:  колонка "convert_id" содержит значения NULL

The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "/home/novikov/work/pycharm-2017.2.3/helpers/pycharm/django_manage.py", line 43, in <module>
    run_module(manage_file, None, '__main__', True)
  File "/home/novikov/.pyenv/versions/3.6.1/lib/python3.6/runpy.py", line 205, in run_module
    return _run_module_code(code, init_globals, run_name, mod_spec)
  File "/home/novikov/.pyenv/versions/3.6.1/lib/python3.6/runpy.py", line 96, in _run_module_code
    mod_name, mod_spec, pkg_name, script_name)
  File "/home/novikov/.pyenv/versions/3.6.1/lib/python3.6/runpy.py", line 85, in _run_code
    exec(code, run_globals)
  File "/home/novikov/work/klever/bridge/manage.py", line 27, in <module>
    execute_from_command_line(sys.argv)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/core/management/__init__.py", line 363, in execute_from_command_line
    utility.execute()
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/core/management/__init__.py", line 355, in execute
    self.fetch_command(subcommand).run_from_argv(self.argv)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/core/management/base.py", line 283, in run_from_argv
    self.execute(*args, **cmd_options)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/core/management/base.py", line 330, in execute
    output = self.handle(*args, **options)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/core/management/commands/migrate.py", line 204, in handle
    fake_initial=fake_initial,
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/migrations/executor.py", line 115, in migrate
    state = self._migrate_all_forwards(state, plan, full_plan, fake=fake, fake_initial=fake_initial)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/migrations/executor.py", line 145, in _migrate_all_forwards
    state = self.apply_migration(state, migration, fake=fake, fake_initial=fake_initial)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/migrations/executor.py", line 244, in apply_migration
    state = migration.apply(state, schema_editor)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/migrations/migration.py", line 129, in apply
    operation.database_forwards(self.app_label, schema_editor, old_state, project_state)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/migrations/operations/fields.py", line 215, in database_forwards
    schema_editor.alter_field(from_model, from_field, to_field)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/backends/base/schema.py", line 513, in alter_field
    old_db_params, new_db_params, strict)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/backends/postgresql/schema.py", line 112, in _alter_field
    new_db_params, strict,
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/backends/base/schema.py", line 674, in _alter_field
    params,
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/backends/base/schema.py", line 119, in execute
    cursor.execute(sql, params)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/backends/utils.py", line 80, in execute
    return super(CursorDebugWrapper, self).execute(sql, params)
  File "/home/novikov/work/klever/bridge/bridge/__init__.py", line 39, in execute_wrapper
    return original(*args, **kwargs)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/backends/utils.py", line 65, in execute
    return self.cursor.execute(sql, params)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/utils.py", line 94, in __exit__
    six.reraise(dj_exc_type, dj_exc_value, traceback)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/utils/six.py", line 685, in reraise
    raise value.with_traceback(tb)
  File "/home/novikov/.pyenv/versions/virtual-env-3.6.1/lib/python3.6/site-packages/django/db/backends/utils.py", line 65, in execute
    return self.cursor.execute(sql, params)
django.db.utils.IntegrityError: ОШИБКА:  колонка "convert_id" содержит значения NULL

Actions #31

Updated by Vladimir Gratinskiy over 6 years ago

  • Status changed from Open to Resolved

Fixed. I supposed old convert and comparison functions to be deleted during population, but after it I added migration that expects only new functions.

Actions #32

Updated by Evgeny Novikov over 6 years ago

  • Status changed from Resolved to Open

The suggested fix helped. Now I wait till function descriptions will be updated. BTW, after a unsafes mark is created there is a description of just a comparison function. So, it isn't trivial to understand semantics of a corresponding error trace pattern. It would be great to show a corresponding conversion function description.

Actions #33

Updated by Vladimir Gratinskiy over 6 years ago

Functions descriptions are already updated. You need to populate the DB.

Actions #34

Updated by Evgeny Novikov over 6 years ago

Vladimir Gratinskiy wrote:

Functions descriptions are already updated. You need to populate the DB.

Please, see my notes in the specification.

Actions #35

Updated by Vladimir Gratinskiy over 6 years ago

Fixed.

Actions #36

Updated by Evgeny Novikov over 6 years ago

  • Status changed from Open to Closed

At last this great feature is in master. I merged the branch in 7be2dfbd. Be careful since migrations can destroy your marks in case they refer to functions being deleted. If you really care, create a database dump or download all marks before update!

Actions

Also available in: Atom PDF