TSTP Solution File: SWV014-1 by SPASS---3.9
View Problem
- Process Solution
%------------------------------------------------------------------------------
% File : SPASS---3.9
% Problem : SWV014-1 : TPTP v8.1.0. Released v2.4.0.
% Transfm : none
% Format : tptp
% Command : run_spass %d %s
% Computer : n021.cluster.edu
% Model : x86_64 x86_64
% CPU : Intel(R) Xeon(R) CPU E5-2620 v4 2.10GHz
% Memory : 8042.1875MB
% OS : Linux 3.10.0-693.el7.x86_64
% CPULimit : 300s
% WCLimit : 600s
% DateTime : Wed Jul 20 21:40:57 EDT 2022
% Result : Unsatisfiable 0.18s 0.43s
% Output : Refutation 0.18s
% Verified :
% SZS Type : Refutation
% Derivation depth : 11
% Number of leaves : 20
% Syntax : Number of clauses : 49 ( 17 unt; 0 nHn; 49 RR)
% Number of literals : 126 ( 0 equ; 80 neg)
% Maximal clause size : 6 ( 2 avg)
% Maximal term depth : 6 ( 2 avg)
% Number of predicates : 9 ( 8 usr; 1 prp; 0-1 aty)
% Number of functors : 15 ( 15 usr; 8 con; 0-3 aty)
% Number of variables : 0 ( 0 sgn)
% Comments :
%------------------------------------------------------------------------------
cnf(1,axiom,
party_of_protocol(a),
file('SWV014-1.p',unknown),
[] ).
cnf(2,axiom,
message(sent(a,b,pair(a,an_a_nonce))),
file('SWV014-1.p',unknown),
[] ).
cnf(5,axiom,
party_of_protocol(b),
file('SWV014-1.p',unknown),
[] ).
cnf(6,axiom,
fresh_to_b(an_a_nonce),
file('SWV014-1.p',unknown),
[] ).
cnf(7,axiom,
( ~ fresh_to_b(u)
| ~ message(sent(v,b,pair(v,u)))
| message(sent(b,t,triple(b,generate_b_nonce(u),encrypt(triple(v,u,generate_expiration_time(u)),bt)))) ),
file('SWV014-1.p',unknown),
[] ).
cnf(8,axiom,
( ~ fresh_to_b(u)
| ~ message(sent(v,b,pair(v,u)))
| b_stored(pair(v,u)) ),
file('SWV014-1.p',unknown),
[] ).
cnf(9,axiom,
( ~ b_stored(pair(u,v))
| ~ message(sent(u,b,pair(encrypt(triple(u,w,generate_expiration_time(v)),bt),encrypt(generate_b_nonce(v),w))))
| b_holds(key(w,u)) ),
file('SWV014-1.p',unknown),
[] ).
cnf(14,axiom,
( ~ message(sent(u,v,w))
| intruder_message(w) ),
file('SWV014-1.p',unknown),
[] ).
cnf(15,axiom,
( ~ intruder_message(pair(u,v))
| intruder_message(u) ),
file('SWV014-1.p',unknown),
[] ).
cnf(16,axiom,
( ~ intruder_message(pair(u,v))
| intruder_message(v) ),
file('SWV014-1.p',unknown),
[] ).
cnf(17,axiom,
( ~ intruder_message(triple(u,v,w))
| intruder_message(u) ),
file('SWV014-1.p',unknown),
[] ).
cnf(18,axiom,
( ~ intruder_message(triple(u,v,w))
| intruder_message(v) ),
file('SWV014-1.p',unknown),
[] ).
cnf(19,axiom,
( ~ intruder_message(triple(u,v,w))
| intruder_message(w) ),
file('SWV014-1.p',unknown),
[] ).
cnf(24,axiom,
( ~ intruder_message(u)
| ~ intruder_message(v)
| intruder_message(pair(u,v)) ),
file('SWV014-1.p',unknown),
[] ).
cnf(28,axiom,
( ~ party_of_protocol(u)
| ~ party_of_protocol(v)
| ~ intruder_message(w)
| message(sent(u,v,w)) ),
file('SWV014-1.p',unknown),
[] ).
cnf(29,axiom,
( ~ party_of_protocol(u)
| ~ intruder_message(v)
| intruder_holds(key(v,u)) ),
file('SWV014-1.p',unknown),
[] ).
cnf(30,axiom,
( ~ party_of_protocol(u)
| ~ intruder_message(v)
| ~ intruder_holds(key(w,u))
| intruder_message(encrypt(v,w)) ),
file('SWV014-1.p',unknown),
[] ).
cnf(31,axiom,
a_nonce(an_a_nonce),
file('SWV014-1.p',unknown),
[] ).
cnf(33,axiom,
a_nonce(generate_b_nonce(u)),
file('SWV014-1.p',unknown),
[] ).
cnf(34,axiom,
( ~ intruder_holds(key(u,b))
| ~ b_holds(key(u,a)) ),
file('SWV014-1.p',unknown),
[] ).
cnf(68,plain,
intruder_message(pair(a,an_a_nonce)),
inference(res,[status(thm),theory(equality)],[2,14]),
[iquote('0:Res:2.0,14.0')] ).
cnf(69,plain,
intruder_message(a),
inference(res,[status(thm),theory(equality)],[68,15]),
[iquote('0:Res:68.0,15.0')] ).
cnf(70,plain,
intruder_message(an_a_nonce),
inference(res,[status(thm),theory(equality)],[68,16]),
[iquote('0:Res:68.0,16.0')] ).
cnf(77,plain,
( ~ fresh_to_b(an_a_nonce)
| b_stored(pair(a,an_a_nonce)) ),
inference(res,[status(thm),theory(equality)],[2,8]),
[iquote('0:Res:2.0,8.1')] ).
cnf(79,plain,
b_stored(pair(a,an_a_nonce)),
inference(ssi,[status(thm)],[77,6,31,70]),
[iquote('0:SSi:77.0,6.0,31.0,70.0')] ).
cnf(81,plain,
( ~ party_of_protocol(u)
| ~ intruder_message(v)
| ~ party_of_protocol(u)
| ~ intruder_message(w)
| intruder_message(encrypt(w,v)) ),
inference(res,[status(thm),theory(equality)],[29,30]),
[iquote('0:Res:29.2,30.2')] ).
cnf(82,plain,
( ~ intruder_message(u)
| ~ party_of_protocol(v)
| ~ intruder_message(w)
| intruder_message(encrypt(w,u)) ),
inference(obv,[status(thm),theory(equality)],[81]),
[iquote('0:Obv:81.0')] ).
cnf(83,plain,
( ~ intruder_message(u)
| ~ intruder_message(v)
| intruder_message(encrypt(v,u)) ),
inference(ems,[status(thm)],[82,1]),
[iquote('0:EmS:82.1,1.0')] ).
cnf(93,plain,
( ~ fresh_to_b(an_a_nonce)
| message(sent(b,t,triple(b,generate_b_nonce(an_a_nonce),encrypt(triple(a,an_a_nonce,generate_expiration_time(an_a_nonce)),bt)))) ),
inference(res,[status(thm),theory(equality)],[2,7]),
[iquote('0:Res:2.0,7.1')] ).
cnf(94,plain,
( ~ party_of_protocol(u)
| ~ party_of_protocol(b)
| ~ intruder_message(pair(u,v))
| ~ fresh_to_b(v)
| message(sent(b,t,triple(b,generate_b_nonce(v),encrypt(triple(u,v,generate_expiration_time(v)),bt)))) ),
inference(res,[status(thm),theory(equality)],[28,7]),
[iquote('0:Res:28.3,7.1')] ).
cnf(95,plain,
message(sent(b,t,triple(b,generate_b_nonce(an_a_nonce),encrypt(triple(a,an_a_nonce,generate_expiration_time(an_a_nonce)),bt)))),
inference(ssi,[status(thm)],[93,6,31,70]),
[iquote('0:SSi:93.0,6.0,31.0,70.0')] ).
cnf(96,plain,
( ~ party_of_protocol(u)
| ~ intruder_message(pair(u,v))
| ~ fresh_to_b(v)
| message(sent(b,t,triple(b,generate_b_nonce(v),encrypt(triple(u,v,generate_expiration_time(v)),bt)))) ),
inference(ssi,[status(thm)],[94,5]),
[iquote('0:SSi:94.1,5.0')] ).
cnf(97,plain,
( ~ party_of_protocol(u)
| ~ party_of_protocol(b)
| ~ intruder_message(pair(encrypt(triple(u,v,generate_expiration_time(w)),bt),encrypt(generate_b_nonce(w),v)))
| ~ b_stored(pair(u,w))
| b_holds(key(v,u)) ),
inference(res,[status(thm),theory(equality)],[28,9]),
[iquote('0:Res:28.3,9.1')] ).
cnf(98,plain,
( ~ party_of_protocol(u)
| ~ intruder_message(pair(encrypt(triple(u,v,generate_expiration_time(w)),bt),encrypt(generate_b_nonce(w),v)))
| ~ b_stored(pair(u,w))
| b_holds(key(v,u)) ),
inference(ssi,[status(thm)],[97,5]),
[iquote('0:SSi:97.1,5.0')] ).
cnf(99,plain,
intruder_message(triple(b,generate_b_nonce(an_a_nonce),encrypt(triple(a,an_a_nonce,generate_expiration_time(an_a_nonce)),bt))),
inference(res,[status(thm),theory(equality)],[95,14]),
[iquote('0:Res:95.0,14.0')] ).
cnf(100,plain,
intruder_message(b),
inference(res,[status(thm),theory(equality)],[99,17]),
[iquote('0:Res:99.0,17.0')] ).
cnf(102,plain,
intruder_message(encrypt(triple(a,an_a_nonce,generate_expiration_time(an_a_nonce)),bt)),
inference(res,[status(thm),theory(equality)],[99,19]),
[iquote('0:Res:99.0,19.0')] ).
cnf(106,plain,
( ~ party_of_protocol(u)
| ~ fresh_to_b(v)
| ~ intruder_message(v)
| ~ intruder_message(u)
| message(sent(b,t,triple(b,generate_b_nonce(v),encrypt(triple(u,v,generate_expiration_time(v)),bt)))) ),
inference(sor,[status(thm)],[96,24]),
[iquote('0:SoR:96.1,24.2')] ).
cnf(107,plain,
( ~ party_of_protocol(u)
| ~ intruder_message(encrypt(generate_b_nonce(v),w))
| ~ intruder_message(encrypt(triple(u,w,generate_expiration_time(v)),bt))
| ~ b_stored(pair(u,v))
| b_holds(key(w,u)) ),
inference(sor,[status(thm)],[98,24]),
[iquote('0:SoR:98.1,24.2')] ).
cnf(114,plain,
( ~ party_of_protocol(u)
| ~ fresh_to_b(v)
| ~ intruder_message(v)
| ~ intruder_message(u)
| intruder_message(triple(b,generate_b_nonce(v),encrypt(triple(u,v,generate_expiration_time(v)),bt))) ),
inference(res,[status(thm),theory(equality)],[106,14]),
[iquote('0:Res:106.4,14.0')] ).
cnf(118,plain,
( ~ party_of_protocol(u)
| ~ fresh_to_b(v)
| ~ intruder_message(v)
| ~ intruder_message(u)
| intruder_message(generate_b_nonce(v)) ),
inference(res,[status(thm),theory(equality)],[114,18]),
[iquote('0:Res:114.4,18.0')] ).
cnf(120,plain,
( ~ intruder_message(u)
| ~ fresh_to_b(u)
| intruder_message(generate_b_nonce(u)) ),
inference(ems,[status(thm)],[118,5,100]),
[iquote('0:EmS:118.0,118.3,5.0,100.0')] ).
cnf(125,plain,
( ~ party_of_protocol(u)
| ~ intruder_message(encrypt(triple(u,v,generate_expiration_time(w)),bt))
| ~ intruder_message(generate_b_nonce(w))
| ~ intruder_message(v)
| ~ b_stored(pair(u,w))
| b_holds(key(v,u)) ),
inference(sor,[status(thm)],[107,83]),
[iquote('0:SoR:107.1,83.2')] ).
cnf(128,plain,
( ~ party_of_protocol(a)
| ~ intruder_message(generate_b_nonce(an_a_nonce))
| ~ intruder_message(an_a_nonce)
| ~ b_stored(pair(a,an_a_nonce))
| b_holds(key(an_a_nonce,a)) ),
inference(sor,[status(thm)],[125,102]),
[iquote('0:SoR:125.1,102.0')] ).
cnf(131,plain,
( ~ b_stored(pair(a,an_a_nonce))
| b_holds(key(an_a_nonce,a)) ),
inference(ssi,[status(thm)],[128,6,31,70,33,120,1,69]),
[iquote('0:SSi:128.2,128.1,128.0,6.0,31.0,70.0,33.0,6.0,31.2,70.0,120.0,6.0,31.0,70.0,1.0,69.0')] ).
cnf(132,plain,
b_holds(key(an_a_nonce,a)),
inference(mrr,[status(thm)],[131,79]),
[iquote('0:MRR:131.0,79.0')] ).
cnf(136,plain,
~ intruder_holds(key(an_a_nonce,b)),
inference(res,[status(thm),theory(equality)],[132,34]),
[iquote('0:Res:132.0,34.1')] ).
cnf(140,plain,
( ~ party_of_protocol(b)
| ~ intruder_message(an_a_nonce) ),
inference(res,[status(thm),theory(equality)],[29,136]),
[iquote('0:Res:29.2,136.0')] ).
cnf(141,plain,
$false,
inference(ssi,[status(thm)],[140,6,31,70,5,100]),
[iquote('0:SSi:140.1,140.0,6.0,31.0,70.0,5.0,100.0')] ).
%------------------------------------------------------------------------------
%----ORIGINAL SYSTEM OUTPUT
% 0.11/0.12 % Problem : SWV014-1 : TPTP v8.1.0. Released v2.4.0.
% 0.11/0.13 % Command : run_spass %d %s
% 0.12/0.34 % Computer : n021.cluster.edu
% 0.12/0.34 % Model : x86_64 x86_64
% 0.12/0.34 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz
% 0.12/0.34 % Memory : 8042.1875MB
% 0.12/0.34 % OS : Linux 3.10.0-693.el7.x86_64
% 0.12/0.34 % CPULimit : 300
% 0.12/0.34 % WCLimit : 600
% 0.12/0.34 % DateTime : Wed Jun 15 20:10:59 EDT 2022
% 0.12/0.34 % CPUTime :
% 0.18/0.43
% 0.18/0.43 SPASS V 3.9
% 0.18/0.43 SPASS beiseite: Proof found.
% 0.18/0.43 % SZS status Theorem
% 0.18/0.43 Problem: /export/starexec/sandbox/benchmark/theBenchmark.p
% 0.18/0.43 SPASS derived 56 clauses, backtracked 0 clauses, performed 0 splits and kept 71 clauses.
% 0.18/0.43 SPASS allocated 75888 KBytes.
% 0.18/0.43 SPASS spent 0:00:00.08 on the problem.
% 0.18/0.43 0:00:00.04 for the input.
% 0.18/0.43 0:00:00.00 for the FLOTTER CNF translation.
% 0.18/0.43 0:00:00.00 for inferences.
% 0.18/0.43 0:00:00.00 for the backtracking.
% 0.18/0.43 0:00:00.01 for the reduction.
% 0.18/0.43
% 0.18/0.43
% 0.18/0.43 Here is a proof with depth 6, length 49 :
% 0.18/0.43 % SZS output start Refutation
% See solution above
% 0.18/0.43 Formulae used in the proof : a_is_party_of_protocol_2 a_sent_message_i_to_b_3 b_is_party_of_protocol_8 nonce_a_is_fresh_to_b_9 b_creates_freash_nonces_in_time_10 b_creates_freash_nonces_in_time_11 b_accepts_secure_session_key_12 intruder_can_record_17 intruder_decomposes_pairs_18 intruder_decomposes_pairs_19 intruder_decomposes_triples_20 intruder_decomposes_triples_21 intruder_decomposes_triples_22 intruder_composes_pairs_27 intruder_message_sent_31 intruder_holds_key_32 intruder_key_encrypts_33 an_a_nonce_is_a_nonce_34 generated_times_and_nonces_are_nonces_37 co1_38
% 0.18/0.43
%------------------------------------------------------------------------------