diff --git a/selinux_deprecated.patch b/selinux_deprecated.patch
new file mode 100644
index 0000000..fbce502
--- /dev/null
+++ b/selinux_deprecated.patch
@@ -0,0 +1,49 @@
+diff --git a/userhelper.c b/userhelper.c
+index 4177c89..f2afde7 100644
+--- a/userhelper.c
++++ b/userhelper.c
+@@ -48,8 +48,6 @@
+ 
+ #ifdef WITH_SELINUX
+ #include <selinux/selinux.h>
+-#include <selinux/flask.h>
+-#include <selinux/av_permissions.h>
+ #endif
+ 
+ #include "shvar.h"
+@@ -111,7 +109,7 @@ static int checkAccess(unsigned int selaccess) {
+     struct av_decision avd;
+     int retval = security_compute_av(user_context,
+ 				     user_context,
+-				     SECCLASS_PASSWD,
++				     string_to_security_class("passwd"),
+ 				     selaccess,
+ 				     &avd);
+ 	  
+@@ -2267,7 +2265,8 @@ main(int argc, char **argv)
+ 	const char *new_home_phone;
+ 	const char *new_shell;
+ #ifdef WITH_SELINUX
+-	unsigned perm;
++	security_class_t class;
++	access_vector_t perm;
+ #endif
+ 
+ 	/* State variable we pass around. */
+@@ -2426,12 +2425,13 @@ main(int argc, char **argv)
+ 			user_name = g_strdup(argv[optind]);
+ 
+ #ifdef WITH_SELINUX
++			class = string_to_security_class("passwd");
+ 			if (c_flag) 
+-			  perm = PASSWD__PASSWD;
++			  perm = string_to_av_perm(class, "passwd");
+ 			else if (s_flag)
+-			  perm = PASSWD__CHSH;
++			  perm = string_to_av_perm(class, "chsh");
+ 			else
+-			  perm = PASSWD__CHFN;
++			  perm = string_to_av_perm(class, "chfn");
+ 
+ 			if (is_selinux_enabled() > 0 &&
+ 			    checkAccess(perm)!= 0) {
diff --git a/usermode.spec b/usermode.spec
index bc74a70..e6c6490 100644
--- a/usermode.spec
+++ b/usermode.spec
@@ -1,7 +1,7 @@
 Summary: Tools for certain user account management tasks
 Name: usermode
 Version: 1.112
-Release: 8%{?dist}
+Release: 9%{?dist}
 License: GPLv2+
 URL: https://pagure.io/usermode/
 Source: https://releases.pagure.org/usermode/usermode-%{version}.autotoolized.tar.xz
@@ -12,6 +12,9 @@ Patch0: sysmacros.patch
 # Backport of da01d6325a1a9eb8154abb6a4590c610e8db8ec4
 # - bad FSF address fix
 Patch1: fsfaddr.patch
+# Backport of 48c4085004caad1ec928fa103b7f3e3fe684c826
+# - <selinux/flask.h> and <selinux/av_permissions.h> are now deprecated
+Patch2: selinux_deprecated.patch
 Requires: pam, passwd, util-linux
 # https://lists.fedoraproject.org/archives/list/devel@lists.fedoraproject.org/thread/IJFYI5Q2BYZKIGDFS2WLOBDUSEGWHIKV/
 BuildRequires: gcc
@@ -45,6 +48,7 @@ graphical tools for certain account management tasks.
 %setup -q
 %patch0 -p1
 %patch1 -p1
+%patch2 -p1
 
 %build
 %configure --with-selinux
@@ -98,6 +102,10 @@ done
 %{_datadir}/applications/*
 
 %changelog
+* Wed Sep 09 2020 Jiri Kucera <jkucera@redhat.com> - 1.112-9
+- Do not use deprecated selinux headers
+  Resolves #1865598
+
 * Sat Aug 01 2020 Fedora Release Engineering <releng@fedoraproject.org> - 1.112-8
 - Second attempt - Rebuilt for
   https://fedoraproject.org/wiki/Fedora_33_Mass_Rebuild