Performance problems? #9

thomas-genet · 2022-11-30T14:55:06Z

Hi,

I am trying to use clingo to verify cryptographic protocols and xclingo to produce the trace of the attack (when there is one). However, even if clingo is fast in finding an attack (seconds) xclingo can take a lot of time (hours) to build the trace.

Do you have any hints/ways to accelerate the trace reconstruction step?

I added a typical lp file on which reconstruction is very slow!

Thanks in advance,

Thomas

#const sizeMax=7.

key(kab).
key(kis).

nonce(ni).
nonce(na).

element(X):- key(X).
element(X):- nonce(X).

size(X,1) :- element(X).
size(pair(X,Y),1+Sx+Sy):- element(X), size(X,Sx), size(Y,Sy), Sx+Sy+1<sizeMax.
size(enc(X,Y),1+Sx+Sy):- element(X), size(X,Sx), size(Y,Sy), Sx+Sy+1<sizeMax.

%Initial knowledge
iknows(kis).
iknows(ni).
iknows(enc(kab,pair(na,ni))).
iknows(kab).

% Pairing
%!trace_rule {"% and % -> pair(%,%)",X,Y,X,Y}
iknows(pair(X,Y)) :- element(X), iknows(X), iknows(Y), size(pair(X,Y),S), S<sizeMax.

% Unpairing
%!trace_rule {"pair(%,%) -> %",X,Y,X}
iknows(X) :- iknows(pair(X,Y)).
%!trace_rule {"pair(%,%) -> %",X,Y,Y}
iknows(Y) :- iknows(pair(X,Y)).

% Decyphering
%!trace_rule {"enc(%,%) and % -> %",K,M,K,M}
iknows(M) :- iknows(K), iknows(enc(K,M)).

% Cyphering
%!trace_rule {"% and % -> enc(%,%)",K,M,K,M}
iknows(enc(K,M)) :- iknows(K), key(K), iknows(M), size(enc(K,M),S), S<sizeMax.

attack:- iknows(enc(kis,pair(na,na))).
#show attack/0. %Fast with clingo

%!show_trace attack.

bramucas · 2022-12-02T09:34:56Z

Hi Thomas,

Thank you for reporting :). I'm giving an eye on this.

Could you please let me know which version of xclingo are you using?

thomas-genet · 2022-12-02T09:48:35Z

Dear Brais, Thank you for answering. My version of xclingo is: xclingo 2.0b12 My version of clingo is: 5.4.0 We are giving a try to clingo/xclingo to teach crypto protocols and their verification. We are currently experimenting a bit with other solvers such as z3/cvc4 but we are not pleased with the "explanation" features of them. xclingo would be a nice alternative, even if dealing with finite models. But as I mention there is a very big overhead for the moment. Maybe it is totally due to the complexity of the problem itself but if there are simple solutions to overcome this, I would be very happy! Best regards, Thomas

bramucas · 2023-02-08T11:44:19Z

Hi Thomas,

apologies for the delay.

I found some bugs thanks to your issue thank you 😃
Now I'm obtaining the following output for explaining attack (right now is taking 2 seconds):

Answer: 1
##Explanation: 1.1
  *
  |__"kis and pair(na,na) -> enc(kis,pair(na,na))"
  |  |__"na and na -> pair(na,na)"
  |  |  |__"pair(na,ni) -> na"
  |  |  |  |__"enc(kab,pair(na,ni)) and kab -> pair(na,ni)"

##Total Explanations:   1
Models: 1

Is this what you expected?

This version (2.0b17) is still under testing but I expect to publish it this week.

I'll notify you when it's ready.

Best wishes,
Brais

thomas-genet · 2023-02-08T12:34:30Z

Dear Brais,

This is a very good news! Yes, the trace is exactly what I expected. I am eager to use this new version!

Thank you very much for the debugging! My plan is to use this for teaching, so you are likely to have 100 more new users next year ;-).

Best regards,

Thomas

thomas-genet · 2023-02-16T13:42:13Z

Dear Brais, Any news? I am so eager to try it! ;-) Best regards, Thomas Le 08/02/2023 à 12:44, Brais Muñiz Castro a écrit :

…

Hi Thomas, apologies for the delay. I found some bugs thanks to your issue thank you 😃 Now I'm obtaining the following output for explaining |attack| (right now is taking 2 seconds): ` Answer: 1 ##Explanation: 1.1 * |*"kis and pair(na,na) -> enc(kis,pair(na,na))" | |*"na and na -> pair(na,na)" | | |*"pair(na,ni) -> na" | | | |*"enc(kab,pair(na,ni)) and kab -> pair(na,ni)" ##Total Explanations: 1 Models: 1 ` Is this what you expected? This version (2.0b17) is still under testing but I expect to publish it this week. I'll notify you when it's ready. Best wishes, Brais — Reply to this email directly, view it on GitHub <#9 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AMQ2V33EV6JL5YFWLKDVKJTWWOBJ3ANCNFSM6AAAAAASPXDXSE>. You are receiving this because you authored the thread.Message ID: ***@***.***>

-- Thomas Genet ISTIC/IRISA Campus de Beaulieu, 35042 Rennes cedex, France Tél: +33 (0) 2 99 84 73 44 E-mail: ***@***.*** http://people.irisa.fr/Thomas.Genet

bramucas · 2023-02-17T10:03:31Z

Hi Thomas,

yes! you can update with pip 😄

python -m pip install xclingo==2.0b17

You can come back to previous versions by just changing the version there.

Keep in mind it's still a beta so you may find more bugs.
I'll notify you when more versions are available.

Best regards,
Brais

bramucas · 2023-02-17T10:03:58Z

And please, let me know if you find more performance problems.

It helps us improve the tool.

thomas-genet · 2023-02-17T12:18:51Z

Dear Brais,

Thank you for making it available with pip.
However, I tried it on the above example and it gives me:

bilbao Crypto 17 % xclingo xclingo_example.lp
xclingo version 2.0b17
Reading from xclingo_example.lp
:24:1-7: error: syntax error, unexpected , expecting . or :-

:28:1-7: error: syntax error, unexpected , expecting . or :-

:30:1-7: error: syntax error, unexpected , expecting . or :-

:34:1-7: error: syntax error, unexpected , expecting . or :-

:38:1-7: error: syntax error, unexpected , expecting . or :-

:43:13-19: error: syntax error, unexpected , expecting . or :-

*** ERROR: (xclingo, explainer program) syntax error

Did you change something about the input syntax?

Thomas

bramucas · 2023-02-17T12:42:34Z

Ups. Yes. Last versions changed slightly the syntax for the annotations.
A small example:

person(gabriel;clare).

drive(gabriel).
alcohol(gabriel, 40).
resist(gabriel).

drive(clare).
alcohol(clare, 5).

%!trace_rule {"% drove drunk", P}.
punish(P) :- drive(P), alcohol(P,A), A>30, person(P).

%!trace_rule {"% resisted to authority", P}.
punish(P) :- resist(P), person(P).

%!trace_rule {"% goes to prison",P}.
sentence(P, prison) :- punish(P).

%!trace_rule {"% is innocent by default",P}.
sentence(P, innocent) :- person(P), not punish(P).

%!trace {alcohol(P,A), "% alcohol's level is %",P,A} :- alcohol(P,A).
%!trace {alcohol(P,A), "% was drunk",P} :- alcohol(P,A).

%!show_trace {sentence(P,S)} :- sentence(P,S).
#show sentence/2.

All annotations now end with a dot ..
%!trace, %!show_trace and other annotations now include the affected atoms between curly braces. If you want to instantiate their variable values you can do it by writing a body for the annotation (separated with :-).

This is the adaptation for the code you previously sent 😄 .

#const sizeMax=7.

key(kab).
key(kis).

nonce(ni).
nonce(na).

element(X):- key(X).
element(X):- nonce(X).

size(X,1) :- element(X).
size(pair(X,Y),1+Sx+Sy):- element(X), size(X,Sx), size(Y,Sy), Sx+Sy+1<sizeMax.
size(enc(X,Y),1+Sx+Sy):- element(X), size(X,Sx), size(Y,Sy), Sx+Sy+1<sizeMax.

%Initial knowledge
iknows(kis).
iknows(ni).
iknows(enc(kab,pair(na,ni))).
iknows(kab).

% Pairing
%!trace_rule {"% and % -> pair(%,%)",X,Y,X,Y}.
iknows(pair(X,Y)) :- element(X), iknows(X), iknows(Y), size(pair(X,Y),S), S<sizeMax.

% Unpairing
%!trace_rule {"pair(%,%) -> %",X,Y,X}.
iknows(X) :- iknows(pair(X,Y)).
%!trace_rule {"pair(%,%) -> %",X,Y,Y}.
iknows(Y) :- iknows(pair(X,Y)).

% Decyphering
%!trace_rule {"enc(%,%) and % -> %",K,M,K,M}.
iknows(M) :- iknows(K), iknows(enc(K,M)).

% Cyphering
%!trace_rule {"% and % -> enc(%,%)",K,M,K,M}.
iknows(enc(K,M)) :- iknows(K), key(K), iknows(M), size(enc(K,M),S), S<sizeMax.

attack:- iknows(enc(kis,pair(na,na))).
%#show attack/0. %Fast with clingo

%!show_trace {attack}.

thomas-genet · 2023-02-17T12:44:56Z

OK, it parses but still fails... later :-)

bilbao Crypto 20 % xclingo xclingo_example.lp
xclingo version 2.0b17
Reading from xclingo_example.lp
Traceback (most recent call last):
File "/usr/local/bin/xclingo", line 8, in
sys.exit(main())
File "/usr/local/lib/python3.10/site-packages/xclingo/main.py", line 195, in main
ground_solve_explain(args, unknown_args, programs)
File "/usr/local/lib/python3.10/site-packages/xclingo/main.py", line 157, in ground_solve_explain
xclingo_control = _init_xclingo_control(args, unknown_args, programs)
File "/usr/local/lib/python3.10/site-packages/xclingo/main.py", line 54, in _init_xclingo_control
xclingo_control.add("base", [], program)
File "/usr/local/lib/python3.10/site-packages/xclingo/_main.py", line 72, in add
name, parameters, self.pre_explaining_pipeline.translate(name, program)
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_pipeline.py", line 20, in translate
translation = p.process_program(translation)
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_preprocessor.py", line 64, in process_program
parse_string(
File "/usr/local/lib/python3.10/site-packages/clingo/ast.py", line 1322, in parse_string
_handle_error(
File "/usr/local/lib/python3.10/site-packages/clingo/_internal.py", line 71, in _handle_error
raise handler.error0.with_traceback(handler.error[2])
File "/usr/local/lib/python3.10/site-packages/clingo/ast.py", line 1210, in _pyclingo_ast_callback
callback(AST(ast))
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_preprocessor.py", line 66, in
lambda ast: self._add_to_translation(self.preprocess_rule(ast)),
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_preprocessor.py", line 45, in _add_to_translation
for ra in rule_asts:
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_preprocessor.py", line 264, in preprocess_rule
for r in self.translate_rule(rule_id, 0, rule_ast.head, rule_ast.body):
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_preprocessor.py", line 200, in translate_rule
for translated_rule in self._support_translator.translate(
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_translator.py", line 87, in translate
yield self._rule(
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/xclingo_ast/_xclingo_ast.py", line 137, in init
super().init(**kwargs)
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/xclingo_ast/_xclingo_ast.py", line 111, in init
super().init(**kwargs)
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/xclingo_ast/_xclingo_ast.py", line 89, in init
super().init(func_name=_SUP_HEAD, **kwargs)
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/xclingo_ast/_xclingo_ast.py", line 80, in init
[rule_id, disjunction_id, head, list(collect_free_vars(body))],
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/xclingo_ast/_ast_shortcuts.py", line 123, in collect_free_vars
if lit.atom.left.ast_type == ASTType.Variable:
File "/usr/local/lib/python3.10/site-packages/clingo/ast.py", line 970, in getattr
raise AttributeError(f"no attribute: {name}")
AttributeError: no attribute: left

bramucas · 2023-02-17T12:56:37Z

Interesting. The code I sent you is working fine for me with version 2.0b17.

Are you running the same code? If not, could you send it to me?

Thank you Thomas

thomas-genet · 2023-02-17T15:45:29Z

Yes it is the same code. I even tried with the smaller example that you provided above and I get the same failure:

bilbao Crypto 4 % xclingo xclingo_example2.lp
xclingo version 2.0b17
Reading from xclingo_example2.lp
Traceback (most recent call last):
File "/usr/local/bin/xclingo", line 8, in
sys.exit(main())
File "/usr/local/lib/python3.10/site-packages/xclingo/main.py", line 195, in main
ground_solve_explain(args, unknown_args, programs)
File "/usr/local/lib/python3.10/site-packages/xclingo/main.py", line 157, in ground_solve_explain
xclingo_control = _init_xclingo_control(args, unknown_args, programs)
File "/usr/local/lib/python3.10/site-packages/xclingo/main.py", line 54, in _init_xclingo_control
xclingo_control.add("base", [], program)
File "/usr/local/lib/python3.10/site-packages/xclingo/_main.py", line 72, in add
name, parameters, self.pre_explaining_pipeline.translate(name, program)
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_pipeline.py", line 20, in translate
translation = p.process_program(translation)
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_preprocessor.py", line 64, in process_program
parse_string(
File "/usr/local/lib/python3.10/site-packages/clingo/ast.py", line 1322, in parse_string
_handle_error(
File "/usr/local/lib/python3.10/site-packages/clingo/_internal.py", line 71, in _handle_error
raise handler.error0.with_traceback(handler.error[2])
File "/usr/local/lib/python3.10/site-packages/clingo/ast.py", line 1210, in _pyclingo_ast_callback
callback(AST(ast))
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_preprocessor.py", line 66, in
lambda ast: self._add_to_translation(self.preprocess_rule(ast)),
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_preprocessor.py", line 45, in _add_to_translation
for ra in rule_asts:
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_preprocessor.py", line 264, in preprocess_rule
for r in self.translate_rule(rule_id, 0, rule_ast.head, rule_ast.body):
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_preprocessor.py", line 200, in translate_rule
for translated_rule in self._support_translator.translate(
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/_translator.py", line 87, in translate
yield self._rule(
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/xclingo_ast/_xclingo_ast.py", line 137, in init
super().init(**kwargs)
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/xclingo_ast/_xclingo_ast.py", line 111, in init
super().init(**kwargs)
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/xclingo_ast/_xclingo_ast.py", line 89, in init
super().init(func_name=_SUP_HEAD, **kwargs)
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/xclingo_ast/_xclingo_ast.py", line 80, in init
[rule_id, disjunction_id, head, list(collect_free_vars(body))],
File "/usr/local/lib/python3.10/site-packages/xclingo/preprocessor/xclingo_ast/_ast_shortcuts.py", line 123, in collect_free_vars
if lit.atom.left.ast_type == ASTType.Variable:
File "/usr/local/lib/python3.10/site-packages/clingo/ast.py", line 970, in getattr
raise AttributeError(f"no attribute: {name}")
AttributeError: no attribute: left

thomas-genet · 2023-02-17T15:49:55Z

Can it be related to a different clingo version or a bad connection to python. The version of clingo that I have in my path is:

bilbao Crypto 6 % clingo --version
clingo version 5.4.0
Address model: 64-bit

libclingo version 5.4.0
Configuration: without Python, with Lua 5.3.4

libclasp version 3.3.5 (libpotassco version 1.1.0)
Configuration: WITH_THREADS=1
Copyright (C) Benjamin Kaufmann

License: The MIT License https://opensource.org/licenses/MIT

bramucas · 2023-02-21T08:37:16Z

clingo 5.5 is needed. Please install it.

You can install clingo from pip or conda without affecting your current installation.

thomas-genet · 2023-02-27T09:46:13Z

Dear Brais,

This is fixed using a correct version of clingo. I used: python3 -m pip install clingo==5.5.0.post3. And now this is working smoothly! Thanks again!

Thomas

bramucas · 2023-02-27T13:00:06Z

Nice.

Still, there will probably be more bugs. We are still facing some of them.

Please if you find more, tell us.

Thank you very much!
Thomas.

bramucas self-assigned this Dec 2, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Performance problems? #9

Performance problems? #9

thomas-genet commented Nov 30, 2022

bramucas commented Dec 2, 2022

thomas-genet commented Dec 2, 2022 via email •

edited

Loading

bramucas commented Feb 8, 2023 •

edited

Loading

thomas-genet commented Feb 8, 2023

thomas-genet commented Feb 16, 2023 via email

bramucas commented Feb 17, 2023

bramucas commented Feb 17, 2023

thomas-genet commented Feb 17, 2023

bramucas commented Feb 17, 2023 •

edited

Loading

thomas-genet commented Feb 17, 2023

bramucas commented Feb 17, 2023

thomas-genet commented Feb 17, 2023

thomas-genet commented Feb 17, 2023 •

edited

Loading

bramucas commented Feb 21, 2023

thomas-genet commented Feb 27, 2023

bramucas commented Feb 27, 2023

Performance problems? #9

Performance problems? #9

Comments

thomas-genet commented Nov 30, 2022

bramucas commented Dec 2, 2022

thomas-genet commented Dec 2, 2022 via email • edited Loading

bramucas commented Feb 8, 2023 • edited Loading

thomas-genet commented Feb 8, 2023

thomas-genet commented Feb 16, 2023 via email

bramucas commented Feb 17, 2023

bramucas commented Feb 17, 2023

thomas-genet commented Feb 17, 2023

*** ERROR: (xclingo, explainer program) syntax error

bramucas commented Feb 17, 2023 • edited Loading

thomas-genet commented Feb 17, 2023

bramucas commented Feb 17, 2023

thomas-genet commented Feb 17, 2023

thomas-genet commented Feb 17, 2023 • edited Loading

bramucas commented Feb 21, 2023

thomas-genet commented Feb 27, 2023

bramucas commented Feb 27, 2023

thomas-genet commented Dec 2, 2022 via email •

edited

Loading

bramucas commented Feb 8, 2023 •

edited

Loading

bramucas commented Feb 17, 2023 •

edited

Loading

thomas-genet commented Feb 17, 2023 •

edited

Loading