diff --git a/SOURCES/0001-Make-seinfo-output-predictable.patch b/SOURCES/0001-Make-seinfo-output-predictable.patch
new file mode 100644
index 0000000..aa650fe
--- /dev/null
+++ b/SOURCES/0001-Make-seinfo-output-predictable.patch
@@ -0,0 +1,90 @@
+From 8ed316d6bfb65e5e9b57f3761ea8490022ab3a05 Mon Sep 17 00:00:00 2001
+From: Petr Lautrbach <plautrba@redhat.com>
+Date: Thu, 18 Nov 2021 13:59:08 +0100
+Subject: [PATCH] Make seinfo output predictable
+
+There are few places where frozenset is used. Given that frozenset is an unordered
+collection the output generated from this is unpredictable.
+
+The following command outputs are fixed using sorted() on frozensets:
+
+    seinfo --constrain
+    seinfo --common
+    seinfo -c -x
+    seinfo -r -x
+    seinfo -u -x
+
+Fixes: https://github.com/SELinuxProject/setools/issues/65
+
+Signed-off-by: Petr Lautrbach <plautrba@redhat.com>
+---
+ setools/policyrep/constraint.pxi | 2 +-
+ setools/policyrep/objclass.pxi   | 4 ++--
+ setools/policyrep/role.pxi       | 2 +-
+ setools/policyrep/user.pxi       | 2 +-
+ 4 files changed, 5 insertions(+), 5 deletions(-)
+
+diff --git a/setools/policyrep/constraint.pxi b/setools/policyrep/constraint.pxi
+index 01c63d87425b..0b4c5b9bcf6a 100644
+--- a/setools/policyrep/constraint.pxi
++++ b/setools/policyrep/constraint.pxi
+@@ -72,7 +72,7 @@ cdef class Constraint(BaseConstraint):
+ 
+     def statement(self):
+         if len(self.perms) > 1:
+-            perms = "{{ {0} }}".format(' '.join(self.perms))
++            perms = "{{ {0} }}".format(' '.join(sorted(self.perms)))
+         else:
+             # convert to list since sets cannot be indexed
+             perms = list(self.perms)[0]
+diff --git a/setools/policyrep/objclass.pxi b/setools/policyrep/objclass.pxi
+index b7ec7b7de5c3..8ed2be5a9bed 100644
+--- a/setools/policyrep/objclass.pxi
++++ b/setools/policyrep/objclass.pxi
+@@ -75,7 +75,7 @@ cdef class Common(PolicySymbol):
+         return other in self.perms
+ 
+     def statement(self):
+-        return "common {0}\n{{\n\t{1}\n}}".format(self, '\n\t'.join(self.perms))
++        return "common {0}\n{{\n\t{1}\n}}".format(self, '\n\t'.join(sorted(self.perms)))
+ 
+ 
+ cdef class ObjClass(PolicySymbol):
+@@ -204,7 +204,7 @@ cdef class ObjClass(PolicySymbol):
+ 
+         # a class that inherits may not have additional permissions
+         if len(self.perms) > 0:
+-            stmt += "{{\n\t{0}\n}}".format('\n\t'.join(self.perms))
++            stmt += "{{\n\t{0}\n}}".format('\n\t'.join(sorted(self.perms)))
+ 
+         return stmt
+ 
+diff --git a/setools/policyrep/role.pxi b/setools/policyrep/role.pxi
+index 9a0dd39f27d9..3af8a3f72a1f 100644
+--- a/setools/policyrep/role.pxi
++++ b/setools/policyrep/role.pxi
+@@ -58,7 +58,7 @@ cdef class Role(PolicySymbol):
+         if count == 1:
+             stmt += " types {0}".format(types[0])
+         else:
+-            stmt += " types {{ {0} }}".format(' '.join(types))
++            stmt += " types {{ {0} }}".format(' '.join(sorted(types)))
+ 
+         stmt += ";"
+         return stmt
+diff --git a/setools/policyrep/user.pxi b/setools/policyrep/user.pxi
+index 9c82aa92eb72..e37af2939820 100644
+--- a/setools/policyrep/user.pxi
++++ b/setools/policyrep/user.pxi
+@@ -81,7 +81,7 @@ cdef class User(PolicySymbol):
+         if count == 1:
+             stmt += roles[0]
+         else:
+-            stmt += "{{ {0} }}".format(' '.join(roles))
++            stmt += "{{ {0} }}".format(' '.join(sorted(roles)))
+ 
+         if self._level:
+             stmt += " level {0.mls_level} range {0.mls_range};".format(self)
+-- 
+2.33.1
+
diff --git a/SPECS/setools.spec b/SPECS/setools.spec
index 30f8027..2b49bef 100644
--- a/SPECS/setools.spec
+++ b/SPECS/setools.spec
@@ -3,7 +3,7 @@
 
 Name:           setools
 Version:        4.4.0
-Release:        3%{?dist}
+Release:        4%{?dist}
 Summary:        Policy analysis tools for SELinux
 
 License:        GPLv2
@@ -11,6 +11,7 @@ URL:            https://github.com/SELinuxProject/setools/wiki
 Source0:        https://github.com/SELinuxProject/setools/archive/%{version}.tar.gz
 Source1:        setools.pam
 Source2:        apol.desktop
+Patch0001:      0001-Make-seinfo-output-predictable.patch
 Patch1002:      1002-Do-not-export-use-setools.InfoFlowAnalysis-and-setoo.patch
 Patch1003:      1003-Require-networkx-on-package-level.patch
 Obsoletes:      setools < 4.0.0, setools-devel < 4.0.0
@@ -141,6 +142,10 @@ Python modules designed to facilitate SELinux policy analysis.
 %{_mandir}/ru/man1/apol*
 
 %changelog
+* Fri Nov 19 2021 Petr Lautrbach <plautrba@redhat.com> - 4.4.0-4
+- Make seinfo output predictable
+  https://github.com/SELinuxProject/setools/issues/65
+
 * Tue Aug 10 2021 Mohan Boddu <mboddu@redhat.com> - 4.4.0-3
 - Rebuilt for IMA sigs, glibc 2.34, aarch64 flags
   Related: rhbz#1991688